動態規劃的狀態轉移：從問題到狀態轉移方程的過程

動態規劃通過拆分問題、存儲中間結果避免重複計算，適用於有重疊子問題和最優子結構的場景。其核心是“狀態轉移”，即不同階段狀態間的推導關係。以爬樓梯爲例：定義`dp[i]`爲爬到第`i`級臺階的方法數，轉移方程爲`dp[i] = dp[i-1] + dp[i-2]`，初始條件`dp[0]=1`（0級臺階1種方法）、`dp[1]=1`（1級臺階1種方法）。另一拓展例子（零錢兌換）中，`dp[i]`表示湊`i`元的最少硬幣數，轉移方程爲`dp[i] = min(dp[i-coin]+1)`（`coin`爲可用面額），初始條件`dp[0]=0`，其餘爲無窮大。初學者需掌握“定義狀態→找轉移關係→寫方程”，通過練習熟悉狀態轉移思維。動態規劃本質是“空間換時間”，狀態轉移方程是連接中間結果的橋樑。