Dynamic Programming 動態規劃視覺化
費波那契
LCS
硬幣找零
費波那契數列
遞迴 O(2^n) vs DP O(n) - 看 DP 如何避免重複計算
計算 fib(
)
開始
遞迴（重複計算）
計算次數:
0
時間複雜度:
O(2^n)
DP（記住結果）
計算次數:
0
時間複雜度:
O(n)
DP 表格:
結果:
-
// dp[i] = dp[i-1] + dp[i-2]
最長共同子序列 (LCS)
找兩個字串中最長的共同子序列
字串1:
字串2:
開始
DP 表格:
LCS:
-
長度:
-
// 如果字元相同: dp[i][j] = dp[i-1][j-1] + 1
// 如果不同: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
硬幣找零
用最少的硬幣組成目標金額
硬幣:
金額:
開始
DP 表格 (最少硬幣數):
結果:
-
// dp[i] = min(dp[i], dp[i - coin] + 1)