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