更新次數：0
上列為索引 i（0 起算），下列為 dp[i] 的值；尚未計算的格顯示空白。
你有沒有算過爬樓梯有幾種走法，卻發現同一段樓梯被自己重複數了好多遍？動態規劃（Dynamic Programming）就是專治這種「一直重算同一件事」的浪費：把算過的小答案先記在一張表上，像記帳時把小計寫在便利貼，下次要用就直接翻表、不必從頭再算一次。代價是得多花一點空間存那張表，換來的是把原本會爆炸成天文數字的計算量壓回可以接受的範圍。下面用費波那契、LCS、硬幣找零三個經典例子，一格一格帶你看這張表是怎麼被填滿的。
動態規劃（Dynamic Programming）用於解決具備以下兩個性質的問題：
dp[i] = f(dp[i-1], dp[i-2], ...)），
每個子問題只算一次，之後直接查表複用，把原本指數級的計算量壓到多項式級。
下面用三個經典範例逐格展示 DP 表如何被填滿：一維遞推（費波那契）、二維填表 + 回溯（LCS）、
以及帶不可達狀態的一維最佳化（硬幣找零）。
一維 DP：dp[i] = dp[i-1] + dp[i-2]，每個 dp[i] 只計算一次，之後查表複用。
二維 DP：dp[i][j] 為 s1 前 i 字元與 s2 前 j 字元的 LCS 長度；填完表後從右下角回溯，
相等處走斜角並收入字元，否則走較大的鄰格，還原出實際的最長共同子序列字串。
一維 DP：dp[i] = min(dp[i], dp[i-coin] + 1)，dp[0] = 0，其餘初始為「不可達」（∞）。
逐一嘗試每種硬幣，若能讓 dp[i] 變小就更新；最終 dp[amount] 仍是 ∞ 代表湊不出目標金額。