一、動態規劃概述

動態規劃（Dynamic Programming，DP）是一種解決復雜問題的高效算法，通過將問題分解為相互重疊的子問題，并存儲子問題的解來避免重復計算。它在眾多領域如計算機科學、運籌學、經濟學等都有廣泛應用，能夠顯著提升問題的求解效率。

核心思想：

1. 最優子結構：問題的最優解包含子問題的最優解。這意味著可以通過求解子問題的最優解來得到原問題的最優解。例如，在求解最短路徑問題時，從起點到終點的最短路徑必然包含了從起點到中間某點的最短路徑。
2. 重疊子問題：不同的問題會重復使用相同的子問題解。如果不進行處理，這些子問題會被多次求解，造成大量的時間浪費。動態規劃通過記錄子問題的解，避免了這種重復計算。
3. 狀態轉移：通過狀態轉移方程描述問題間的遞推關系。狀態轉移方程是動態規劃的核心，它定義了如何從已知的子問題解推導出當前問題的解。

適用場景：

• 最優化問題（最大值 / 最小值）：例如求最大利潤、最短路徑等。在資源分配問題中，需要在一定的約束條件下，找到使某個目標函數達到最大值或最小值的方案。
• 計數問題（多少種方式）：比如計算排列組合的數量、走樓梯的不同方式等。這類問題通常需要統計滿足特定條件的所有可能情況的數量。
• 存在性問題（是否可行）：判斷是否存在滿足某種條件的解。例如，在背包問題中，判斷是否能在給定的背包容量下裝入某些物品。

二、動態規劃三要素

1. DP 數組定義：明確dp[i]或dp[i][j]表示的含義。dp數組用于存儲子問題的解，其定義需要根據具體問題來確定。例如，在斐波那契數列問題中，dp[i]表示第i個斐波那契數。
2. 狀態轉移方程：描述問題間的遞推關系。它是動態規劃的關鍵，通過狀態轉移方程，可以從已知的子問題解推導出當前問題的解。狀態轉移方程的推導需要對問題進行深入分析，找出問題之間的內在聯系。
3. 初始條件：確定最小子問題的解。初始條件是動態規劃的基礎，它為狀態轉移提供了起點。在很多問題中，初始條件通常是邊界情況的解。

三、經典 DP 問題實現

3.1 斐波那契數列（LeetCode 509）

斐波那契數列是一個經典的數學序列，其定義為：F(0)=0，F(1)=1，F(n)=F(n?1)+F(n?2)（n≥2）。

class Solution {public int fib(int n) {if (n <= 1) return n;int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}// 空間優化版public int fibOptimized(int n) {if (n <= 1) return n;int prev = 0, curr = 1;for (int i = 2; i <= n; i++) {int sum = prev + curr;prev = curr;curr = sum;}return curr;}
}

在上述代碼中，fib方法使用了一個一維數組dp來存儲中間結果，避免了重復計算。而fibOptimized方法則對空間進行了優化，只使用了兩個變量prev和curr來保存必要的信息，將空間復雜度從O(n)降低到了O(1)。

3.2 爬樓梯（LeetCode 70）

假設你正在爬樓梯，需要n階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

class Solution {public int climbStairs(int n) {if (n <= 2) return n;int[] dp = new int[n+1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

這個問題可以轉化為斐波那契數列問題。到達第n階樓梯的方法數等于到達第n - 1階樓梯的方法數加上到達第n - 2階樓梯的方法數。

四、二維 DP 問題

4.1 最小路徑和（LeetCode 64）

給定一個包含非負整數的m x n網格grid，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。每次只能向下或者向右移動一步。

class Solution {public int minPathSum(int[][] grid) {int m = grid.length, n = grid[0].length;int[][] dp = new int[m][n];// 初始化dp[0][0] = grid[0][0];for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];// 狀態轉移for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];}}return dp[m-1][n-1];}
}

在這個問題中，dp[i][j]表示從左上角到達坐標(i, j)的最小路徑和。通過初始化第一行和第一列的dp值，然后使用狀態轉移方程dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]來更新其他位置的dp值。

4.2 最長公共子序列（LeetCode 1143）

給定兩個字符串text1和text2，返回這兩個字符串的最長公共子序列的長度。

class Solution {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length(), n = text2.length();int[][] dp = new int[m+1][n+1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i-1) == text2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[m][n];}
}

dp[i][j]表示text1的前i個字符和text2的前j個字符的最長公共子序列的長度。如果text1的第i個字符和text2的第j個字符相等，則dp[i][j] = dp[i-1][j-1] + 1；否則，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])。

五、背包問題系列

5.1 0 - 1 背包問題

給定一組物品，每個物品有對應的重量weights和價值values，以及一個容量為capacity的背包。要求在不超過背包容量的前提下，選擇一些物品放入背包，使得背包中物品的總價值最大。每個物品只能選擇放入或不放入背包（即 0 - 1 選擇）。

class Knapsack {public int maxValue(int[] weights, int[] values, int capacity) {int n = weights.length;int[][] dp = new int[n+1][capacity+1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= capacity; j++) {if (j < weights[i-1]) {dp[i][j] = dp[i-1][j];} else {dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weights[i-1]] + values[i-1]);}}}return dp[n][capacity];}// 空間優化版（一維數組）public int maxValueOptimized(int[] weights, int[] values, int capacity) {int[] dp = new int[capacity+1];for (int i = 0; i < weights.length; i++) {for (int j = capacity; j >= weights[i]; j--) {dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]);}}return dp[capacity];}
}

在maxValue方法中，dp[i][j]表示前i個物品在背包容量為j時的最大價值。通過兩層循環遍歷物品和背包容量，根據當前物品是否能放入背包來更新dp值。maxValueOptimized方法對空間進行了優化，使用一維數組dp來保存中間結果，將空間復雜度從O(n?capacity)降低到了O(capacity)。

5.2 完全背包問題（LeetCode 322 零錢兌換）

給定不同面額的硬幣coins和一個總金額amount，編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。每種硬幣的數量是無限的。

import java.util.Arrays;class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];Arrays.fill(dp, amount+1); // 初始化為最大值dp[0] = 0;for (int coin : coins) {for (int i = coin; i <= amount; i++) {dp[i] = Math.min(dp[i], dp[i-coin] + 1);}}return dp[amount] > amount ? -1 : dp[amount];}
}

dp[i]表示湊成金額i所需的最少硬幣個數。通過遍歷每種硬幣，更新dp數組。如果dp[amount]仍然大于amount，說明無法湊成總金額，返回 -1。

六、DP 解題方法論

6.1 解題步驟

1. 確定 DP 狀態：明確狀態表示什么含義。這是解決動態規劃問題的關鍵一步，需要根據問題的特點來定義合適的狀態。
2. 定義 DP 數組：選擇一維 / 二維數組存儲狀態。根據問題的復雜度和狀態的維度，選擇合適的數組來存儲中間結果。
3. 狀態轉移方程：找出狀態間的關系式。通過分析問題的最優子結構，推導出狀態轉移方程。
4. 初始化：確定邊界條件。初始化是狀態轉移的起點，需要根據問題的定義來確定邊界情況的解。
5. 計算順序：確定填表順序。根據狀態轉移方程的依賴關系，確定計算dp數組的順序。
6. 空間優化：考慮是否可降維。在一些情況下，可以通過優化空間來降低算法的空間復雜度。

6.2 經典問題分類

問題類型	典型例題	特點
線性 DP	最長遞增子序列 (300)	單序列或雙序列問題
區間 DP	最長回文子串 (5)	涉及子區間的最優解
樹形 DP	打家劫舍 III (337)	在樹結構上進行狀態轉移
狀態機 DP	買賣股票最佳時機 (121)	狀態間存在多種轉移可能
數位 DP	數字 1 的個數 (233)	處理數字位上的計數問題

七、高頻面試題精選

7.1 編輯距離（LeetCode 72）

給你兩個單詞word1和word2，請你計算出將word1轉換成word2所使用的最少操作數。你可以對一個單詞進行如下三種操作：插入一個字符、刪除一個字符、替換一個字符。

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] dp = new int[m+1][n+1];// 初始化for (int i = 1; i <= m; i++) dp[i][0] = i;for (int j = 1; j <= n; j++) dp[0][j] = j;// 狀態轉移for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i-1) == word2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1]) + 1;}}}return dp[m][n];}
}

dp[i][j]表示將word1的前i個字符轉換成word2的前j個字符所需的最少操作數。通過初始化第一行和第一列的dp值，然后使用狀態轉移方程來更新其他位置的dp值。

7.2 打家劫舍（LeetCode 198）

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組nums，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

class Solution {public int rob(int[] nums) {int n = nums.length;if (n == 0) return 0;if (n == 1) return nums[0];int[] dp = new int[n];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < n; i++) {dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[n-1];}// 空間優化版public int robOptimized(int[] nums) {int prev = 0, curr = 0;for (int num : nums) {int temp = Math.max(curr, prev + num);prev = curr;curr = temp;}return curr;}
}

rob方法使用一維數組dp來存儲中間結果，dp[i]表示偷竊前i間房屋能夠獲得的最高金額。robOptimized方法對空間進行了優化，只使用兩個變量prev和curr來保存必要的信息。

八、DP 優化技巧

1. 空間壓縮：二維轉一維（滾動數組）。在一些問題中，dp數組的更新只依賴于前一行或前幾行的信息，此時可以使用滾動數組將二維數組壓縮為一維數組，從而降低空間復雜度。
2. 狀態壓縮：用位運算表示狀態（如 TSP 問題）。對于一些狀態數量較少的問題，可以使用位運算來表示狀態，從而減少空間的使用。
3. 單調隊列優化：優化滑動窗口最值問題。在求解滑動窗口的最值問題時，可以使用單調隊列來優化時間復雜度。
4. 斜率優化：優化特定形式的狀態轉移方程。對于一些具有特定形式的狀態轉移方程，可以使用斜率優化來降低時間復雜度。

// 示例：使用滾動數組優化空間
int[][] dp = new int[2][n]; // 只保留前兩行

九、常見誤區與調試技巧

常見錯誤：

1. 未正確處理邊界條件。邊界條件是動態規劃的基礎，如果處理不當，會導致結果錯誤。
2. 狀態轉移方程推導錯誤。狀態轉移方程是動態規劃的核心，如果推導錯誤，整個算法將無法得到正確的結果。
3. 數組越界訪問。在使用dp數組時，需要注意數組的下標范圍，避免越界訪問。
4. 空間復雜度過高。在一些問題中，如果沒有進行空間優化，可能會導致空間復雜度過高，從而超出內存限制。

調試建議：

1. 打印 DP 表格檢查中間結果。通過打印dp數組的中間結果，可以幫助我們理解狀態轉移的過程，發現問題所在。
2. 從小規模測試用例開始驗證。先使用小規模的測試用例來驗證算法的正確性，逐步增加測試用例的規模。
3. 使用 IDE 的調試功能逐步跟蹤。利用 IDE 的調試功能，逐步執行代碼，觀察變量的變化，找出問題所在。
4. 對比暴力解法的結果。如果可能的話，可以實現一個暴力解法，將其結果與動態規劃的結果進行對比，驗證算法的正確性。

十、學習路徑建議

1. 基礎階段：

   • 斐波那契數列
   • 爬樓梯問題
   • 最小路徑和
     這些問題是動態規劃的基礎，通過解決這些問題，可以幫助我們理解動態規劃的基本思想和解題步驟。

2. 進階階段：

   • 背包問題系列
   • 股票買賣問題
   • 字符串 DP 問題
     這些問題具有一定的復雜度，需要我們深入理解狀態設計和轉移方程的構建。

3. 高手階段：

   • 樹形 DP
   • 狀態壓縮 DP
   • 數位 DP
     這些問題是動態規劃的高級應用，需要我們具備較強的思維能力和編程技巧。

結語

動態規劃是算法學習中的難點也是重點，需要大量練習才能掌握其精髓。建議從簡單問題入手，逐步理解狀態設計和轉移方程的構建，最終達到能夠獨立解決陌生 DP 問題的水平。