動態規劃是解決複雜問題的一種常用方法，它通過拆分問題，存儲中間結果，避免重複計算，從而提高效率。而“狀態轉移”是動態規劃的核心環節，它描述了問題中不同階段的狀態之間如何相互影響、相互推導。對於初學者來說，理解如何從問題本身一步步推導出狀態轉移方程，是掌握動態規劃的關鍵。
一、動態規劃與狀態轉移的核心思想¶
動態規劃通常用於解決具有重疊子問題和最優子結構的問題。例如，求斐波那契數列、爬樓梯、零錢兌換等。其核心在於：將複雜問題分解爲多個簡單的子問題，通過存儲子問題的解（即“狀態”），避免重複計算，最終推導出原問題的解。
狀態轉移是連接這些子問題解的“橋樑”。它描述了：當前狀態如何由前一個或多個狀態推導而來。
二、從問題到狀態轉移方程的步驟（以“爬樓梯”爲例）¶
我們以“爬樓梯問題”作爲具體例子，詳細拆解“從問題到狀態轉移方程”的過程：
問題：假設你需要爬n級臺階，每次可以爬1級或2級，問有多少種不同的方法？
步驟1：明確問題，識別子問題¶
要解決“n級臺階的方法數”，觀察發現：
- 最後一步只能是從n-1級爬1級，或從n-2級爬2級（最優子結構）。
- 因此，方法數 = 爬到n-1級的方法數 + 爬到n-2級的方法數（重疊子問題，如n=3時，n-1=2和n-2=1會重複計算）。
步驟2：定義狀態¶
設dp[i]表示“爬到第i級臺階的方法數”。
- dp[i]是對“第i級臺階”這個階段的量化描述，是我們需要計算的核心。
步驟3：推導狀態轉移方程¶
根據步驟1的分析，爬到第i級臺階的方法數，由兩種情況疊加而成：
- 從i-1級爬1級：方法數爲dp[i-1]；
- 從i-2級爬2級：方法數爲dp[i-2]。
因此，狀態轉移方程爲：
dp[i] = dp[i-1] + dp[i-2]
步驟4：確定初始條件和邊界¶
狀態轉移需要“起點”，即最基礎的狀態值：
- dp[0] = 1（定義“0級臺階”爲1種方法，作爲遞推起點）；
- dp[1] = 1（1級臺階只有1種方法：直接爬1級）。
步驟5：計算結果¶
有了狀態轉移方程和初始條件，即可逐步計算：
- dp[2] = dp[1] + dp[0] = 1 + 1 = 2（2級臺階：1+1或2）；
- dp[3] = dp[2] + dp[1] = 2 + 1 = 3（3級臺階：1+1+1、1+2、2+1）；
- 以此類推，dp[n]即爲n級臺階的方法數。
三、另一個例子：零錢兌換問題（拓展）¶
問題：給定硬幣面額[1,2,5]，總金額n，求湊出總金額最少需要多少枚硬幣？若無法湊出，返回-1。
步驟1：定義狀態¶
設dp[i]表示“湊出金額i所需的最少硬幣數”。
步驟2：推導轉移方程¶
要湊出金額i，最後一步可用任意麪額coin，此時前面金額爲i-coin，因此：
dp[i] = min(dp[i-coin] + 1)（若i >= coin且dp[i-coin]存在）。
步驟3：初始條件¶
dp[0] = 0（金額0無需硬幣）；- 其他金額初始化爲無窮大（表示“未湊出”）。
步驟4：計算結果（以n=5爲例）¶
dp[0] = 0；dp[1] = dp[0] + 1 = 1（用1枚1元）；dp[2] = min(dp[1]+1, dp[0]+1) = 1（用1枚2元）；dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1（用1枚5元）。
四、初學者的關鍵總結¶
- 定義狀態是基礎：用
dp[i]清晰描述問題的階段（如“湊出金額i”“爬到臺階i”）。 - 轉移方程是核心：通過分析“最後一步如何到達當前狀態”，找到狀態間的依賴關係（如
dp[i] = dp[i-1] + dp[i-2]）。 - 初始條件不可少：從最基礎的狀態值（如
dp[0]）開始遞推，避免推導時出錯。 - 多練習積累經驗：通過爬樓梯、零錢兌換、最長遞增子序列等問題，逐步熟悉狀態轉移的思維。
動態規劃的本質是“用空間換時間”，通過存儲中間結果避免重複計算，而狀態轉移方程就是連接這些結果的橋樑。只要掌握“定義狀態→找轉移關係→寫方程”的三步法，就能逐步攻克動態規劃的核心！