0. 學習目標

動態規劃 (Dynamic Programming, DP) 是解決最優化問題的一種重要方法，它通過將原問題分解為相對簡單的子問題的方式來求解復雜問題。動態規劃在計算機科學、運籌學、經濟學等領域有著廣泛的應用。
通過本節學習，應掌握以下內容：

• 動態規劃的基本概念和核心思想
• 動態規劃與分治法的區別
• 動態規劃的適用條件
• 動態規劃的基本步驟和實現方法
• 典型動態規劃問題的分析與解決

1. 動態規劃的基本概念

1.1 什么是動態規劃

動態規劃是一種數學優化方法和算法范式，用于通過將復雜問題分解為更簡單的子問題，并利用子問題的最優解來構造原問題的最優解?。在計算機科學中，如果問題滿足最優子結構 (Optimal Substructure) 和重疊子問題 (Overlapping Subproblems) 兩大屬性，則可采用動態規劃進行求解?。

1.2 動態規劃的核心思想

動態規劃基于以下兩個核心思想：

• 最優子結構：整體問題的最優解可以由各子問題的最優解組合而成。當子問題的最優解能夠以某種方式拼合出原問題的最優