Dynamic Programming

solve complex problem by breaking it into sub-problem and stores the results of subproblems to avoid computing the same results again.

Divide-and-Conquer + Memorization
用memory把算出來的結果記下來(空間換時間)
flow: read data -> calculate data-> store data

適合的題目性質:
1. Overlapping Subproblems
2. Optimal Substructure

• Overlapping Subproblems

• 只用Divide-and-Conquer Method

缺點: 已經算出答案的還是需要重算
ex: fib(3) 出現2次, 第一次就算出答案, 第二次遇到還是要重算

• Memorization

1. Top Down:
   check lookup table
   是initial value -> 計算 -> 存到lookup table
   不是initial value -> 回傳value

table有可能跳過幾個沒算到
ex: 求table[20], table[13], table[17]沒用到就不會算

2. Down Top:
table從小到大的數字一個個算出來

• 重要議題: 節省記憶體

ref:

Overlapping Subproblems Property in Dynamic Programming | DP-1 - GeeksforGeeks

• 經典問題

1. 不重複組合（ Combination ）
2. 河內塔（ Tower of Hanoi ）

1. 樓梯路線（ Staircase Walk ），計數問題

只能往右or往下走

矩陣相乘, Hamilton Path….
To be continue

Dynamic Programming - 演算法筆記

• Optimal Substructure

最佳解 = 最佳解_sub1 + 最佳解_sub2

ex:
shortest path: x -> v -> u
x -> u 最短路徑 = x -> v 最短路徑 + v -> u 最短路徑

Note: longest path 沒有 optimal substructure

https://www.geeksforgeeks.org/optimal-substructure-property-in-dynamic-programming-dp-2/