計算思維訓練(動態規劃)

史釙鐳王靜張婧穎薛誌堅謝誌鋒

出版商: 東南大學
出版日期: 2026-01-01
售價: $336
語言: 簡體中文
頁數: 249
ISBN: 7576625112
ISBN-13: 9787576625110
相關分類: Algorithms-data-structures

下單後立即進貨 (約4週~6週)

商品描述

動態規劃（Dynamic Programming，簡稱DP）是一種具有廣泛應用價值的算法思想，不僅在數學、計算機科學等領域占據重要地位，還在經濟學、生物信息學等其他學科中展現出廣闊的應用前景。本書全面介紹了動態規劃的基礎概念，並深入探討了多種經典模型，如線性DP、狀態壓縮DP、區間DP、樹形DP、背包問題、數位DP、插頭DP、計數DP、動態DP及概率DP等。此外，書中還介紹了常用的優化方法，如線段樹、單調隊列、斜率優化、凸殼優化、四邊形不等式等數據結構優化技巧。本書系統歸類並總結了歷年CSP／NOIP比賽中出現的動態規劃問題，涵蓋其定義、核心思想、求解過程以及問題分類和解法分析。每章內容均包含知識點講解、例題及問題分析，並配套習題分析和參考程序等豐富資源。本書適合已掌握C＋＋程序設計語言並開始學習算法的青少年編程愛好者，尤其適用於準備參加CSP-J／S及NOIP比賽的讀者。

目錄大綱

第1章線性動態規劃
1.1 一維線性動態規劃
1.2 加維
1.3 內存優化
總結和拓展
習題1
第2章背包問題
2.1 0-1背包問題
2.2 多重背包問題
2.3 完全背包問題
2.4 背包的空間優化
總結和拓展
習題2
第3章區間動態規劃
3.1 區間動態規劃基礎
3.2 區間動態規劃應用
3.3 區間動態規劃優化
總結和拓展
習題3
第4章計數動態規劃
4.1 排列中的計數
4.2 組合中的計數
4.3 樹圖類計數
總結和拓展
習題4
第5章樹形動態規劃
5.1 樹形動態規劃基礎
5.2 樹上二次掃描換根
總結和拓展
習題5
第6章位運算及其狀態壓縮
6.1 位運算基礎
6.2 bitset及其應用
6.3 位運算及搜索
6.4 狀態壓縮動態規劃
總結和拓展
習題6
第7章單調隊列優化
7.1 單調隊列基礎
7.2 單調隊列優化的經典問題
7.3 單調隊列優化的擴展應用
總結和拓展
習題7
習題解析
參考文獻