信息學(xué)競賽寶典 動態(tài)規(guī)劃
定 價：69.9 元
- 作者：張新華 胡向榮 伍婉秋
- 出版時間：2024/2/1
- ISBN：9787115620361
- 出 版 社：人民郵電出版社
- 中圖法分類：TP3
- 頁碼：212
- 紙張：
- 版次：01
- 開本：16開
動態(tài)規(guī)劃（Dynamic Programming，DP；簡稱動規(guī)）在算法競賽中占據(jù)極其重要的位置，也是初學(xué)者在剛接觸算法設(shè)計時覺得難以理解的知識點。簡單來說，動態(tài)規(guī)劃是一種用來解決最優(yōu)化問題的算法思想，將一個復(fù)雜的問題分解成若干個子問題，通過綜合子問題的最優(yōu)解來得到原問題的最優(yōu)解，通常適用于解決有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。
為了幫助初學(xué)者理解動態(tài)規(guī)劃，本書直接以各類競賽真題入手，全面細致地介紹算法競賽中經(jīng)常用到的各類動態(tài)規(guī)劃算法模型。為了讀者能更深刻地理解和掌握其算法思想內(nèi)涵，本書精挑細選、由淺入深地安排了相關(guān)習(xí)題。
● 難得一見的動態(tài)規(guī)劃算法專項訓(xùn)練書
● 直接以各類競賽真題入手
● 配有 PPT+ 源碼 + 講解視頻
● 提供對應(yīng)在線題庫
1.代碼精煉、語言簡練、內(nèi)容全面、擅長將復(fù)雜的算法思想用淺顯的圖文形式描述。
2.講解細致，關(guān)鍵代碼有注釋，有行號便于教師講解，采用專業(yè)等寬編程字體，對初學(xué)者易犯的錯誤有提醒。
3.注重思維訓(xùn)練，一題多解，培養(yǎng)用數(shù)學(xué)思維解題。
4.全套經(jīng)過多次校驗過的精練代碼參考及測試數(shù)據(jù)。
5.配有視頻講解，完整展示解題過程。
6.作者在算法競賽領(lǐng)域有著多年的積累。
張新華
中學(xué)高級教師，信息學(xué)競賽教練。取得浙江大學(xué)計算機科學(xué)與技術(shù)學(xué)士學(xué)位、廈門大學(xué)軟件工程碩士學(xué)位，獲得 2009年普通高中信息技術(shù)現(xiàn)場優(yōu)質(zhì)課比賽全國一等獎。培養(yǎng)的學(xué)生多次獲得全國青少年奧林匹克聯(lián)賽國家一等獎及亞太與太平洋地區(qū)信息學(xué)奧林匹克競賽獎牌。著有“信息學(xué)競賽寶典”系列書。開發(fā)了三維圖形化 C++ 編程工具 Dev-C++ 智能開發(fā)平
臺和 Python 可視化界面設(shè)計軟件 Visual Python。
胡向榮
安徽省信息學(xué)競賽金牌教練。獲得中國首屆網(wǎng)絡(luò)管理員大賽亞軍，安徽省首屆計算機技術(shù)大賽一等獎，安徽省信息技術(shù)優(yōu)質(zhì)課評選一等獎。安慶市教育技術(shù)專家、信息技術(shù)學(xué)科骨干教師、先進教研個人。
伍婉秋
初中信息技術(shù)一級教師，廣州市白云區(qū)永平片初二信息技術(shù)教研組組長；參與教育部全國教育科學(xué)“十三五”規(guī)劃課題“三維圖形化智能編程系統(tǒng)在中小學(xué)編程教育中的構(gòu)建和應(yīng)用”；曾獲廣州市中學(xué)信息技術(shù)教師教學(xué)能力比賽二等獎、白云區(qū)一等獎。
目錄
CONTENTS
第 1章 最長不下降子序列問題
1.1.最長不下降子序列 / 1
1.2.抄近路 / 6
1.3.寶藏 / 7
1.4.導(dǎo)彈攔截 / 8
1.5.和諧俱樂部 / 9
1.6.滑雪 / 10
1.7.拓展與練習(xí) / 12
第 2章 背包問題
2.1.簡單背包問題 / 13
2.2.0/1背包問題 / 15
2.3.0/1背包算法的優(yōu)化 / 17
2.4.分組背包問題 / 18
2.4.1.二維數(shù)組動態(tài)規(guī)劃算法 / 19
2.4.2.一維數(shù)組優(yōu)化算法 / 20
2.5.拓展與練習(xí) / 21
第3章 完全背包問題
3.1.完全背包 / 22
3.2.完全背包算法的優(yōu)化 / 23
3.3.拓展與練習(xí) / 24
第4章 多重背包問題
4.1.多重背包 / 25
4.2.通天塔 / 27
4.3.忙碌 / 28
4.4.拓展與練習(xí) / 29
第5章 二維費用背包問題
5.1.訓(xùn)練賽 / 30
5.2.電腦游戲 / 31
5.3.拓展與練習(xí) / 32
第6章 區(qū)間動態(tài)規(guī)劃
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.拓展與練習(xí) / 54
第7章 路徑問題
7.1.最短路徑 / 55
7.2.最少交通費用問題 / 60
7.3.拓展與練習(xí) / 62
第8章 資源類動態(tài)規(guī)劃
8.1.機器分配 / 63
8.2.調(diào)度問題 / 64
8.3.系統(tǒng)可靠性 / 66
8.4.購物 / 67
8.5.快餐問題 / 69
8.6.拓展與練習(xí) / 71
第9章 動態(tài)規(guī)劃的簡單優(yōu)化
9.1.絲綢之路 / 72
9.1.1.動態(tài)規(guī)劃算法一 / 73
9.1.2.動態(tài)規(guī)劃算法二 / 73
9.1.3.動態(tài)規(guī)劃算法三 / 74
9.2.雙人游戲 / 75
9.2.1.動態(tài)規(guī)劃算法一 / 76
9.2.2.動態(tài)規(guī)劃算法二 / 76
9.3.理想收入問題 / 77
9.3.1.樸素算法 / 78
9.3.2.優(yōu)化算法一 / 78
9.3.3.優(yōu)化算法二 / 79
9.3.4.優(yōu)化算法三 / 80
9.3.5.優(yōu)化算法四 / 80
9.3.6.貪心算法 / 81
9.4.唱片錄制 / 82
9.4.1.動態(tài)規(guī)劃算法一 / 83
9.4.2.動態(tài)規(guī)劃算法二 / 84
9.4.3.動態(tài)規(guī)劃算法三 / 85
9.5.相遇問題 / 86
9.5.1.動態(tài)規(guī)劃算法 / 87
9.5.2.普通遞歸算法 / 89
9.5.3.優(yōu)化遞歸算法 / 91
9.5.4.寬度優(yōu)先搜索算法 / 92
9.5.5.動態(tài)規(guī)劃算法的優(yōu)化 / 93
9.6.拓展與練習(xí) / 96
第 10章 最大連續(xù)子序列問題
10.1.最大連續(xù)子序列和 / 97
10.2.最大連續(xù)子序列積 / 98
10.3.k個最大連續(xù)子序列和 / 99
10.4.拓展與練習(xí) / 101
第 11章 子矩陣問題
11.1.二維最大子矩陣問題 / 102
11.2.擴展最大子矩陣問題 / 104
11.3.子矩陣變形問題 / 105
11.4.拓展與練習(xí) / 107
第 12章 子序列問題
12.1.最長前綴 / 108
12.2.zipper / 110
12.3.最長公共子序列 / 111
12.3.1.動態(tài)規(guī)劃算法一 / 112
12.3.2.動態(tài)規(guī)劃算法二 / 115
12.4.確定基因功能 / 115
12.5.最長公共上升子序列 / 118
12.5.1.基本算法 / 119
12.5.2.優(yōu)化算法 / 120
12.6.拓展與練習(xí) / 122
第 13章 雙重動態(tài)規(guī)劃
13.1.城市交通 / 123
13.2.復(fù)雜的審批 / 126
13.3.拓展與練習(xí) / 128
第 14章 多進程動態(tài)規(guī)劃
14.1.方格取數(shù) / 129
14.2.三取方格數(shù) / 132
14.3.拓展與練習(xí) / 134
第 15章 樹形動態(tài)規(guī)劃
15.1.加分二叉樹 / 135
15.2.寶藏 / 137
15.3.選課 / 141
15.4.沒有上司的舞會 / 144
15.5.拓展與練習(xí) / 146
第 16章 數(shù)位動態(tài)規(guī)劃
16.1.包含49 / 147
16.2.幸運數(shù)字 / 152
16.3.拓展與練習(xí) / 155
第 17章 狀態(tài)壓縮動態(tài)規(guī)劃
17.1.混亂的隊伍 / 156
17.2.放置猛獸一 / 158
17.3.放置猛獸二 / 160
17.4.炮兵陣地 / 162
17.5.清掃計劃 / 164
17.6.拓展與練習(xí) / 166
第 18章 動態(tài)規(guī)劃的高級優(yōu)化
18.1.單調(diào)隊列優(yōu)化 / 167
18.1.1.最大子序列和 / 167
18.1.2.烽火傳遞 / 169
18.1.3.多重背包 / 171
18.1.4.紀念手表 / 174
18.2.四邊形不等式優(yōu)化 / 175
18.2.1.歸并石子3 / 175
18.2.2.破壞鐵路 / 178
18.2.3.分段 / 179
18.3.斜率優(yōu)化 / 180
18.4.拓展與練習(xí) / 184
第 19章 綜合訓(xùn)練
19.1.逢低吸納 / 185
19.2.紅牌 / 186
19.3.點菜 / 187
19.4.選數(shù)統(tǒng)計 / 187
19.5.烏龜棋 / 188
19.6.守望者的逃離 / 189
19.7.三角形最大面積 / 190
19.8.積木游戲 / 191
19.9.多米諾骨牌 / 192
19.10.最大子樹和 / 193
19.11.訪問美術(shù)館 / 194
19.12.花園 / 194
19.13.旅行計劃 / 195
19.14.垃圾井 / 196
19.15.重建道路 / 197
19.16.迎接儀式 / 198
19.17.棋盤制作 / 199
19.18.打磚塊 / 200
19.19.血緣關(guān)系 / 201
19.20.集合方案數(shù) / 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
書單推薦
