信息學競賽寶典 動態規劃

動態規劃（Dynamic Programming，DP；簡稱動規）在算法競賽中占據極其重要的位置，也是初學者在剛接觸算法設計時覺得難以理解的知識點。簡單來說，動態規劃是一種用來解決最優化問題的算法思想，將一個復雜的問題分解成若乾個子問題，通過綜合子問題的最優解來得到原問題的最優解，通常適用於解決有重疊子問題和最優子結構性質的問題。

為了幫助初學者理解動態規劃，本書直接以各類競賽真題入手，系統細致地介紹算法競賽中經常用到的各類動態規劃算法模型。為了讀者能更深刻地理解和掌握其算法思想內涵，本書精挑細選、由淺入深地安排了相關習題。

张新华

中学高级教师，信息学竞赛教练。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位，获得 2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年奥林匹克联赛国家一等奖及亚太与太平洋地区信息学奥林匹克竞赛奖牌。著有“信息学竞赛宝典”系列书。开发了三维图形化 C++ 编程工具 Dev-C++ 智能开发平

台和 Python 可视化界面设计软件 Visual Python。

胡向荣

安徽省信息学竞赛金牌教练。获得中国首届网络管理员大赛亚军，安徽省首届计算机技术大赛一等奖，安徽省信息技术优质课评选一等奖。安庆市教育技术专家、信息技术学科骨干教师、先进教研个人。

伍婉秋

初中信息技术一级教师，广州市白云区永平片初二信息技术教研组组长；参与教育部全国教育科学“十三五”规划课题“三维图形化智能编程系统在中小学编程教育中的构建和应用”；曾获广州市中学信息技术教师教学能力比赛二等奖、白云区一等奖。

目錄

CONTENTS

第 1章　最長不下降子序列問題

1.1.最長不下降子序列　/　1

1.2.抄近路　/　6

1.3.寶藏　/　7

1.4.導彈攔截　/　8

1.5.和諧俱樂部　/　9

1.6.滑雪　/　10

1.7.拓展與練習　/　12

第 2章 背包問題

2.1.簡單背包問題　/　13

2.2.0/1背包問題　/　15

2.3.0/1背包算法的優化　/　17

2.4.分組背包問題　/　18

2.4.1.二維數組動態規劃算法　/　19

2.4.2.一維數組優化算法　/　20

2.5.拓展與練習　/　21

第3章 完全背包問題

3.1.完全背包　/　22

3.2.完全背包算法的優化　/　23

3.3.拓展與練習 　/　24

第4章 多重背包問題

4.1.多重背包　/　25

4.2.通天塔　/　27

4.3.忙碌　/　28

4.4.拓展與練習　/　29

第5章 二維費用背包問題

5.1.訓練賽　/　30

5.2.電腦游戲　/　31

5.3.拓展與練習　/　32

第6章 區間動態規劃

6.1.書架問題1　/　33

6.2.書架問題2　/　35

6.3.收購珍珠　/　37

6.4.雙色馬　/　38

6.5.歸並石子１　/　39

6.6.切割銅棒　/　44

6.7.郵局問題　/　45

6.8.乘積最大　/　47

6.9.凸多邊形三角劃分　/　49

6.10.凸多邊形分割　/　51

6.11.拓展與練習　/　54

第7章 路徑問題

7.1.最短路徑　/　55

7.2.最少交通費用問題　/　60

7.3.拓展與練習　/　62

第8章 資源類動態規劃

8.1.機器分配　/　63

8.2.調度問題　/　64

8.3.系統可靠性　/　66

8.4.購物　/　67

8.5.快餐問題　/　69

8.6.拓展與練習　/　71

第9章 動態規劃的簡單優化

9.1.絲綢之路　/　72

9.1.1.動態規劃算法一　/　73

9.1.2.動態規劃算法二　/　73

9.1.3.動態規劃算法三　/　74

9.2.雙人游戲　/　75

9.2.1.動態規劃算法一　/　76

9.2.2.動態規劃算法二　/　76

9.3.理想收入問題　/　77

9.3.1.樸素算法　/　78

9.3.2.優化算法一　/　78

9.3.3.優化算法二　/　79

9.3.4.優化算法三　/　80

9.3.5.優化算法四　/　80

9.3.6.貪心算法　/　81

9.4.唱片錄制　/　82

9.4.1.動態規劃算法一　/　83

9.4.2.動態規劃算法二　/　84

9.4.3.動態規劃算法三　/　85

9.5.相遇問題　/　86

9.5.1.動態規劃算法　/　87

9.5.2.普通遞歸算法　/　89

9.5.3.優化遞歸算法　/　91

9.5.4.寬度優先搜索算法　/　92

9.5.5.動態規劃算法的優化　/　93

9.6.拓展與練習　/　96

第 10章 最大連續子序列問題

10.1.最大連續子序列和　/　97

10.2.最大連續子序列積　/　98

10.3.k個最大連續子序列和　/　99

10.4.拓展與練習　/　101

第 11章 子矩陣問題

11.1.二維最大子矩陣問題　/　102

11.2.擴展最大子矩陣問題　/　104

11.3.子矩陣變形問題　/　105

11.4.拓展與練習　/　107

第 12章 子序列問題

12.1.最長前綴　/　108

12.2.zipper　/　110

12.3.最長公共子序列　/　111

12.3.1.動態規劃算法一　/　112

12.3.2.動態規劃算法二　/　115

12.4.確定基因功能　/　115

12.5.最長公共上升子序列　/　118

12.5.1.基本算法　/　119

12.5.2.優化算法　/　120

12.6.拓展與練習　/　122

第 13章 雙重動態規劃

13.1.城市交通　/　123

13.2.復雜的審批　/　126

13.3.拓展與練習　/　128

第 14章 多進程動態規劃

14.1.方格取數　/　129

14.2.三取方格數　/　132

14.3.拓展與練習　/　134

第 15章 樹形動態規劃

15.1.加分二叉樹　/　135

15.2.寶藏　/　137

15.3.選課　/　141

15.4.沒有上司的舞會　/　144

15.5.拓展與練習　/　146

第 16章 數位動態規劃

16.1.包含49　/　147

16.2.幸運數字　/　152

16.3.拓展與練習　/　155

第 17章 狀態壓縮動態規劃

17.1.混亂的隊伍　/　156

17.2.放置猛獸一　/　158

17.3.放置猛獸二　/　160

17.4.炮兵陣地　/　162

17.5.清掃計劃　/　164

17.6.拓展與練習　/　166

第 18章 動態規劃的高級優化

18.1.單調隊列優化　/　167

18.1.1.最大子序列和　/　167

18.1.2.烽火傳遞　/　169

18.1.3.多重背包　/　171

18.1.4.紀念手錶　/　174

18.2.四邊形不等式優化　/　175

18.2.1.歸並石子3　/　175

18.2.2.破壞鐵路　/　178

18.2.3.分段　/　179

18.3.斜率優化　/　180

18.4.拓展與練習　/　184

第 19章 綜合訓練

19.1.逢低吸納　/　185

19.2.紅牌　/　186

19.3.點菜　/　187

19.4.選數統計　/　187

19.5.烏龜棋　/　188

19.6.守望者的逃離　/　189

19.7.三角形最大面積　/　190

19.8.積木游戲　/　191

19.9.多米諾骨牌　/　192

19.10.最大子樹和　/　193

19.11.訪問美術館　/　194

19.12.花園　/　194

19.13.旅行計劃　/　195

19.14.垃圾井　/　196

19.15.重建道路　/　197

19.16.迎接儀式　/　198

19.17.棋盤製作　/　199

19.18.打磚塊　/　200

19.19.血緣關系　/　201

19.20.集合方案數　/　202

19.21.基因序列　/　203

19.22.基因武器　/　204

19.23.壓路機　/　204

19.24.旅行商　/　206

19.25.二叉蘋果樹　/　207

19.26.技能樹　/　208

19.27.騎士　/　209

19.28.猛獸動物園　/　210