動態規劃簡介 (Dynamic Programming Intro)
動態規劃 (Dynamic Programming, DP) 和分治法相似，會把問題分解成若干個子問題，不同的是，DP 的子問題往往都是不獨立，子問題需要依靠其他子問題的解。
性質
- 重複子問題：相同的一個子問題，會被重複計算多次。
- 最佳子結構：問題的最佳解包含子問題的最佳解。
- 無後效性：子問題一旦確被定後，就不會被改變，不會被之後更大的問題所影響。
技巧：空間換取時間(記憶化搜索)
為避免相同子問題多次計算，會使用陣列(記憶體)記住答案，提高計算效率。
步驟
- 定義狀態：要如何記錄問題的答案。通常定義 ，為算出答案的函數。
- 訂出初始狀態。
- 訂出轉移式：如何從其他狀態轉移到當前狀態。
時間/空間複雜度計算
時間複雜度：狀態個數 轉移複雜度。 狀態個數絕大多數可由開的陣列大小得知。 轉移複雜度：最多一個狀態需要花費多少時間計算。