#42849: 動態規劃五步法
chiuliyou@gmail.com
(邱立宇)
學校
:
新北市立永平高級中學
編號 : 136609
來源 : [61.228.158.165]
最後登入時間 ：
2024-10-26 13:36:59
1. 構造問題: 輸出走到右下角的最小總和
2. 定義狀態: f(i, j) 表示走道座標 i, j 的最小總和
3. 求解小規模的簡單問題:
f(0, 0) = 0
f(0, j) = 列總和
f(i, 0) = 行總和
4. 狀態轉移方程式:
f(i, j) = min(f(i - 1, j), f(i, j - 1)) + grid[i][j]
5. 判斷複雜度: O(n)