動態規劃 Dynamic Programming

1. Wiki 定義： https://en.wikipedia.org/wiki/Dynamic_programming
2. “Simplifying a complicated problem by breaking it down into simpler sub-problems” (in a recursive manner)
3. Divide & Conquer + Optimal substructure

分治 + 最優子結構

關鍵點

動態規劃 和 遞歸或者分治 沒有根本上的區別（關鍵看有無最優的子結構）

共性：找到重複子問題

差異性：最優子結構、中途可以淘汰次優解

例題

1. 最優子結構 opt[n] = best_of(opt[n-1], opt[n-2], ...)
2. 儲存中間狀態：opt[i]
3. 遞推公式（美其名曰：狀態轉移方程或者 DP 方程）

Fib: opt[i] = opt[n-1] + opt[n-2]

二維路徑：opt[i,j] = opti+1 + opti (且判斷a[i,j]是否空地）