信息学奥赛2：121道题零基础吃透高级算法与数据结构（视频教程+代码详解+刻意练习）

（1）大量图示使知识表达直观清晰。
（2）语言简明易懂、讲解细致，便于理解复杂概念。
（3）知识覆盖面广，讲解深入。
（4）提供完整、可编译运行的C++代码。

本书是一本针对信息学奥赛CSP-J考试进行多种算法题型讲解类书籍，也是本系列共三本书籍中的第2本。
全书分两部分共8章。其中第一部分（第1～第4章）针对的是动态规划算法题型的讲解，内容包括：路径或网
格行走问题、序列问题、决策制定问题、背包问题、区间动态规划问题、分割问题、编辑距离问题、计数问题。第
二部分（第5～第8章）针对的是四种重要数据结构（包括栈、队列、树、图）的讲解。全书共计安排了信息学奥赛
中121道经典题型的解析。
本书既适合作为广大信息学奥赛学习者的自学用书和考试刷题用书，也适合作为信息学奥赛CSP-J考试培训的
参考教材。

王健伟，毕业于哈尔滨工程大学计算机及应用专业。拥有超过20年软件开发经验，主导或参与过数十个实战项目，技术领域涵盖网络通信、网络安全、网络游戏。曾联合创办知名网络安全公司——安络科技有限公司，并担任中国首套网络安全在线扫描评估系统的项目负责人，以及全球同服独立游戏《冒险之路》的制作人。近八年来，致力于编程教育，迄今已累计培养学员、读者数万名，遍布全球，其中众多学员已就职于国内外知名科技公司。

第一部分 算法刷题之动态规划算法



第1章 动态规划算法简介

1.1 动态规划算法的代码形式4

1.2 动态规划算法的题型特点4

1.3 动态规划算法的解题步骤5

1.4 动态规划算法的题型整理6



第2章 动态规划算法之基本模型

2.1 1258：数字金字塔10

2.2 1259：求最长不下降子序列13

2.3 1260：拦截导弹(Noip1999)16

2.4 1261：城市交通路网18

2.5 1262：挖地雷22

2.6 1263：友好城市24

2.7 1264：合唱队形26

2.8 1265：最长公共子序列29

2.9 1266：设备分配34

2.10 1281：最长上升子序列38

2.11 1282：最大子矩阵39

2.12 1283：登山40

2.13 1284：摘花生44

2.14 1285：最大上升子序列和47

2.15 1286：怪盗基德的滑翔翼49

2.16 1287：最低通行费50

2.17 1288：三角形最佳路径问题52

2.18 1289：拦截导弹56



第3章 动态规划算法之背包问题

3.1 1267： 01背包58

3.2 1268：完全背包问题65

3.3 1269：庆功会（多重背包）69

3.4 1270：混合背包72

3.5 1292：宠物小精灵之收服（二维费用背包）73

3.6 1271：潜水员（二维费用背包）79

3.7 1272：分组背包90

3.8 322题：零钱兑换（完全背包）93

3.9 1273：货币系统（完全背包）95

3.10 1290：采药（01背包）98

3.11 1291：数字组合（01背包）99

3.12 1293：买书（完全背包）102

3.13 1294：Charm Bracelet
（01背包）105

3.14 1295：装箱问题（01背包）106

3.15 1296：开餐馆（不太适合背包）108



第4章 动态规划算法之经典题

4.1 1274：合并石子111

4.2 1275：乘积最大116

4.3 1276：编辑距离118

4.4 1277：方格取数123

4.5 1278：复制书稿(book)127

4.6 1279：橱窗布置(flower)131

4.7 1280：滑雪135

4.8 1297：公共子序列137

4.9 1298：计算字符串距离138

4.10 1299：糖果141

4.11 1300：鸡蛋的硬度143

4.12 1301：大盗阿福（打家劫舍）146

4.13 1302：股票买卖147

4.14 1303：鸣人的影分身152

4.15 1304：数的划分155

4.16 1305：Maximum sum157

4.17 1306：最长公共上升子序列160

4.18 1197：山区建小学164

第二部分 数据结构



第5章 栈

5.1 1331：后缀表达式的值171

5.2 1353：表达式括号匹配(stack)173

5.3 1354：括弧匹配检验174

5.4 1355：字符串匹配问题(strs)174

5.5 1356：计算(calc)176

5.6 1357：车厢调度(train)179

5.7 1358：中缀表达式值(expr)181



第6章 队列

6.1 1332：周末舞会183

6.2 1333：Blah数集185

6.3 1334：围圈报数186

6.4 1335：连通块186

6.5 1359：围成面积188

6.6 1360：奇怪的电梯(lift)190

6.7 1361：产生数(Produce)191

6.8 1362：家庭问题(family)193

6.9 1418：猴子选大王（修改的约瑟夫问题）197



第7章 树

7.1 树的基础概念201

7.2 1336：找树根和孩子202

7.3 1337：单词查找树/字典树/Trie树204

7.4 二叉树的概念208

7.5 1338：医院设置210

7.6 二叉树的遍历213

7.7 1339：求后序遍历216

7.8 扩展二叉树219

7.9 1340：扩展二叉树220

7.10 1363：小球(drop)222

7.11 二叉树的层序遍历225

7.12 1364：二叉树遍历(flist)226

7.13 1365：FBI树(fbi)228

7.14 1366：二叉树输出(btout)230

7.15 1367：查找二叉树(tree_a)232

7.16 1368：对称二叉树(tree_c)233

7.17 1369：合并果子(fruit：小顶堆)234

7.18 1370：最小函数值(minval)240

7.19 1371：看病243

7.20 1372：小明的账单246

7.21 1373：鱼塘钓鱼(fishing）249



第8章 图论算法

8.1 基础知识255

8.2 图的遍历264

8.3 最短路径算法274

8.4 图的连通性331

8.5 并查集354

8.6 最小生成树401

8.7 拓扑排序418