動態規劃-學習筆記

這是一份動態規劃（Dynamic Programming, DP）完整學習筆記。筆記將從一星難度（入門）到五星難度（進階），循序漸進，涵蓋核心思想、經典模型和解題方法論。
本來打算今天更新背包問題的題解的，但事情比較多，就拿一篇筆記來更新吧+_+

動態規劃核心思想 (Pre-Star)

在開始之前，我們必須理解動態規劃的本質。它不是一種特定的算法，而是一種解決問題的思想。

什么是動態規劃？

動態規劃是一種將復雜問題分解成更小的、可重復的子問題，并通過存儲子問題的解來避免重復計算，從而找到原問題最優解的方法。

2. DP 的兩個核心特征：

最優子結構 (Optimal Substructure): 原問題的最優解可以由其子問題的最優解構成。這意味著我們可以通過組合子問題的最優解，來得到原問題的最優解。
重疊子問題 (Overlapping Subproblems): 在問題的求解過程中，許多子問題會被多次重復計算。DP 的高效正體現在它只需計算一次，然后將結果存起來供后續使用。

3. 解題的兩種主要實現方式：

自頂向下 (Top-Down) 與記憶化搜索: 從原問題出發，通過遞歸函數求解。如果遇到已經計算過的子問題，直接返回存儲的結果，否則進行計算并存入備忘錄。
自底向上 (Bottom-Up) 與遞推: 從最小的子問題開始，迭代地計算并填充 DP 表，直到計算出原問題的解。這是更常見、通常也更高效的實現方式。

動態規劃解題五步法 (非常重要！)

幾乎所有的 DP 問題都可以套用以下五個步驟來思考：

定義 dp 數組的含義： 這是最關鍵的一步。明確 dp[i] 或 dp[i][j] 代表什么，比如 dp[i] 是前 i 個元素能獲得的最大價值。
找出遞推關系式（狀態轉移方程）： 這是 DP 的核心。思考 dp[i] 是如何由之前的狀態（如 dp[i-1], dp[i-2] 等）推導出來的。
初始化 dp 數組： 根據遞推公式和 dp 數組的定義，設置好初始值（base case），比如 dp[0] 的值。
確定遍歷順序： 思考是應該從前向后遍歷，還是從后向前，或者二維數組的內外層循環順序。這取決于狀態轉移方程中 dp[i] 依賴于哪些歷史狀態。
根據 dp 數組推導出最終解： 最終答案可能直接是 dp 數組的某個值，也可能是整個數組的最大值。

★☆☆☆☆ (一星): 線性 DP 入門

這個階段主要是理解 DP 的基本思想，通常處理一維數組或序列問題。

經典問題1：斐波那契數列 / 爬樓梯

問題描述 (爬樓梯): 你在爬一個 n 階的樓梯。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂？
五步法分析:
1. dp 定義: dp[i] 表示爬到第 i 階樓梯的不同方法數。
2. 遞推公式: 要到達第 i 階，可以從第 i-1 階爬 1 步上來，也可以從第 i-2 階爬 2 步上來。所以 dp[i] = dp[i-1] + dp[i-2]。
3. 初始化: dp[1] = 1 (爬到第1階只有1種方法)，dp[2] = 2 (可以 1+1 或 2)。
4. 遍歷順序: 從 i = 3 到 n，從前向后遍歷。
5. 最終解: dp[n]。
代碼示例 (C++):

    int climbStairs(int n) {if (n <= 2) return n;std::vector<int> dp(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];}

經典問題2：打家劫舍 (House Robber I)

問題描述: 你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，但相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
五步法分析:
1. dp 定義: dp[i] 表示偷竊前 i 間房屋所能獲得的最大金額。
2. 遞推公式: 對于第 i 間房，你有兩個選擇：
  - 不偷第 i 間: 最大金額等于偷前 i-1 間的最大金額，即 dp[i-1]。
  - 偷第 i 間: 那么第 i-1 間就不能偷，最大金額等于偷前 i-2 間的最大金額加上第 i 間的金額，即 dp[i-2] + nums[i-1] (注意 nums 索引)。
  - 取兩者最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。
3. 初始化: dp[0] = 0 (沒有房子)，dp[1] = nums[0] (只有一間房，必偷)。
4. 遍歷順序: 從 i = 2 到 n，從前向后。
5. 最終解: dp[n]。
代碼示例 (C++):

    int rob(std::vector<int>& nums) {if (nums.empty()) return 0;int n = nums.size();if (n == 1) return nums[0];std::vector<int> dp(n + 1);dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= n; ++i) {dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[n];}

★★☆☆☆ (二星): 二維 DP 與經典模型

這個階段開始引入二維 dp 數組，用于解決需要兩個變量來定義狀態的問題。背包問題是這個階段的重中之重。

經典問題1：不同路徑 (Unique Paths)

問題描述: 一個機器人在一個 m x n 網格的左上角，它每次只能向右或者向下移動一步。機器人試圖達到網格的右下角。問總共有多少條不同的路徑？
五步法分析:
1. dp 定義: dp[i][j] 表示從左上角到達坐標 (i, j) 的路徑數。
2. 遞推公式: 要到達 (i, j)，只能從 (i-1, j) (上面) 或 (i, j-1) (左面) 過來。所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 初始化: 第一行和第一列的所有格子都只有一條路徑到達，所以 dp[i][0] = 1，dp[0][j] = 1。
4. 遍歷順序: 從上到下，從左到右。
5. 最終解: dp[m-1][n-1]。
代碼示例 (C++):

    int uniquePaths(int m, int n) {std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));for (int i = 0; i < m; ++i) dp[i][0] = 1;for (int j = 0; j < n; ++j) dp[0][j] = 1;for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}

經典問題2：0-1 背包問題

問題描述: 有 N 件物品和一個容量為 V 的背包。第 i 件物品的重量是 weight[i]，價值是 value[i]。求解將哪些物品裝入背包，可使這些物品的重量總和不超過背包容量，且價值總和最大。
五步法分析 (二維數組版本):
1. dp 定義: dp[i][j] 表示從前 i 件物品中任意選擇，放入容量為 j 的背包中，所能獲得的最大價值。
2. 遞推公式: 對于第 i 件物品，有兩個選擇：
  - 不放入背包: 最大價值等于只考慮前 i-1 件物品放入容量 j 的背包，即 dp[i-1][j]。
  - 放入背包: (前提是 j >= weight[i])，價值等于只考慮前 i-1 件物品放入容量為 j - weight[i] 的背包的最大價值，再加上第 i 件物品的價值，即 dp[i-1][j - weight[i]] + value[i]。
  - 取兩者最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])。
3. 初始化: dp[0][j] = 0 (不選任何物品，價值為0)。dp[i][0] = 0 (背包容量為0，價值為0)。
4. 遍歷順序: 外層循環物品 i 從 1到 N，內層循環背包容量 j 從 1 到 V。
5. 最終解: dp[N][V]。
代碼示例 (C++，空間優化后的一維數組版本):

一維數組優化是背包問題的精髓。
1. dp 定義: dp[j] 表示容量為 j 的背包所能獲得的最大價值。
2. 遞推公式: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。
3. 初始化: dp 數組全部初始化為 0。
4. 遍歷順序: 外層循環物品 i，內層循環容量 j 必須從后向前遍歷！ 這是為了保證計算 dp[j] 時，所依賴的 dp[j - weight[i]] 還是上一輪 i-1 的狀態。

    void test_01_knapsack(int W, int N, const std::vector<int>& weights, const std::vector<int>& values) {std::vector<int> dp(W + 1, 0);for (int i = 0; i < N; ++i) { // 遍歷物品for (int j = W; j >= weights[i]; --j) { // 遍歷背包容量 (倒序)dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);}}std::cout << "Max value is: " << dp[W] << std::endl;}

★★★☆☆ (三星): 序列 DP 與背包變種

這個階段處理更復雜的序列問題和背包問題的變體，需要更深入的思考狀態定義和轉移。

經典問題1：最長遞增子序列 (Longest Increasing Subsequence)

問題描述: 給定一個整數序列，找到其中最長遞增子序列的長度。子序列不要求連續。
五步法分析 (O(N2) 解法):
1. dp 定義: dp[i] 表示以 nums[i] 結尾的最長遞增子序列的長度。
2. 遞推公式: 對于 nums[i]，我們需要向前遍歷所有 j < i。如果 nums[i] > nums[j]，說明 nums[i] 可以接在以 nums[j] 結尾的遞增子序列后面，形成一個更長的序列。所以 dp[i] = max(dp[i], dp[j] + 1)。
3. 初始化: dp 數組所有元素都初始化為 1，因為每個元素自身都構成一個長度為 1 的遞增子序列。
4. 遍歷順序: 外層循環 i 從 0 到 n-1，內層循環 j 從 0 到 i-1。
5. 最終解: 最終答案是整個 dp 數組中的最大值，而不是 dp[n-1]。
代碼示例 (C++):

    int lengthOfLIS(std::vector<int>& nums) {if (nums.empty()) return 0;int n = nums.size();std::vector<int> dp(n, 1);int max_len = 1;for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {dp[i] = std::max(dp[i], dp[j] + 1);}}max_len = std::max(max_len, dp[i]);}return max_len;}

_注：此問題有更優的 O(NlogN) 解法，使用貪心+二分查找，屬于進階內容。_

經典問題2：完全背包 (Unbounded Knapsack)

問題描述: 與 0-1 背包類似，但每種物品可以無限次地放入背包。
分析: 與 0-1 背包唯一的區別在于，當你考慮第 i 件物品時，你還可以繼續考慮它。這體現在一維 dp 數組的遍歷順序上。
遍歷順序變化: 內層循環容量 j 從前向后遍歷。
- 為什么？ 在計算 dp[j] 時，我們需要用到 dp[j - weight[i]] 的值。在正序遍歷中，dp[j - weight[i]] 已經被本輪（第i件物品）更新過，這等價于第 i 件物品已經被放入過一次，可以再次放入。
代碼示例 (C++):

    void test_unbounded_knapsack(int W, int N, const std::vector<int>& weights, const std::vector<int>& values) {std::vector<int> dp(W + 1, 0);for (int i = 0; i < N; ++i) { // 遍歷物品for (int j = weights[i]; j <= W; ++j) { // 遍歷背包容量 (正序)dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);}}std::cout << "Max value is: " << dp[W] << std::endl;}

★★★★☆ (四星): 復雜狀態與區間 DP

這個階段的問題狀態定義更加復雜，可能包含多個維度，或者需要在一個區間上進行 DP。

經典問題1：股票買賣系列 (Best Time to Buy and Sell Stock)

問題描述: 這是一系列問題，限制了交易次數、引入了冷卻期或手續費。我們以最多交易 K 次為例。
五步法分析:
1. dp 定義: 需要三個維度來定義狀態。dp[i][k][s] 表示第 i 天，最多允許 k 次交易，當前持股狀態為 s (0:不持股, 1:持股) 時所擁有的最大利潤。
2. 遞推公式:
  - dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    
    (今天不持股 = 昨天就不持股，或昨天持股今天賣出)
  - dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
    
    (今天持股 = 昨天就持股，或昨天不持股今天買入。注意買入消耗一次交易，所以是 k-1)
3. 初始化: dp[-1][k][0] = 0, dp[-1][k][1] = -infinity (還沒開始不可能持股)。
4. 遍歷順序: 天數 i 從 0 到 n-1，交易次數 k 從 1 到 K。
5. 最終解: dp[n-1][K][0] (最后一天不持股的利潤一定是最大的)。
這個通用框架可以解決幾乎所有的股票問題，只需要根據題意微調狀態轉移方程即可。

經典問題2：區間 DP (Interval DP)

問題描述 (戳氣球): 有 n 個氣球，編號為 0 到 n-1，每個氣球上都標有一個數字，這些數字存在數組 nums 中。現在要求你戳破所有的氣球。每當你戳破一個氣球 i 時，你將會獲得 nums[left] * nums[i] * nums[right] 個硬幣。這里的 left 和 right 代表和 i 相鄰的兩個氣球的序號。戳破了氣球 i 后，left 和 right 就變成了相鄰的氣球。求所能獲得硬幣的最大數量。
分析: 這個問題如果正向思考（先戳哪個），會發現后續狀態難以確定。反向思考：最后戳哪個氣球？
1. dp 定義: dp[i][j] 表示戳破區間 (i, j) (開區間) 內所有氣球能獲得的最大硬幣數。
2. 遞推公式: 假設在區間 (i, j) 中，我們最后戳破的氣球是 k (i < k < j)。那么此時 i 和 j 就是 k 相鄰的氣球。戳破 k 的收益是 nums[i] * nums[k] * nums[j]。而在這之前，區間 (i, k) 和 (k, j) 的氣球已經被戳破了，這兩部分是獨立的。所以 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]) for k in (i, j)。
3. 初始化: dp 數組初始化為 0。為了方便處理邊界，可以在 nums 數組兩邊各加一個 1。
4. 遍歷順序: 區間 DP 的遍歷順序很特別。外層循環是區間的長度 len (從 3 到 n)，內層循環是區間的起始點 i。這樣保證在計算大區間 dp[i][j] 時，所有它依賴的小區間都已經計算完畢。
5. 最終解: dp[0][n-1] (n是新數組的長度)。

★★★★★ (五星): 狀態壓縮與樹形/圖 DP

這是 DP 的最高境界，通常與位運算、圖論、樹等結構結合，解決 NP-Hard 問題在小規模數據下的最優解。

經典問題1：狀態壓縮 DP (Bitmask DP)

適用場景: 當問題中某個維度的狀態數量不多 (通常 Nle20)，且每個狀態可以用二進制位來表示（是/否，用過/沒用過）時。
問題描述 (旅行商問題 TSP): 給定 n 個城市和一個距離矩陣，求從一個城市出發，訪問所有其他城市一次后回到出發點的最短路徑。
分析:
1. dp 定義: dp[mask][i] 表示訪問過的城市集合為 mask (一個整數，其二進制表示中第 j 位為 1 代表城市 j 已訪問)，當前停留在城市 i 時的最短路徑長度。
2. 遞推公式: 要從狀態 dp[mask][i] 轉移，我們可以枚舉下一個要去的城市 j。前提是 j 不在 mask 集合中。
  - dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])
3. 初始化: dp[1 << start_node][start_node] = 0。
4. 遍歷順序: 外層循環 mask 從 1 到 (1 << n) - 1，中層循環當前城市 i，內層循環下一個城市 j。
5. 最終解: min(dp[(1 << n) - 1][i] + dist[i][start_node]) for all i。

經典問題2：樹形 DP (Tree DP)

適用場景: 在樹形結構上求解最優問題。
問題描述 (打家劫舍 III): 房屋排列成二叉樹結構。如果偷竊了某個節點，就不能偷竊其直接相連的子節點。求最大偷竊金額。
分析:
1. dp 定義: 對于每個節點 u，我們需要知道兩個狀態：偷它和不偷它能得到的最大收益。所以定義一個 pair 或大小為 2 的數組 dp[u]。dp[u][0] 表示不偷 u 時，在以 u 為根的子樹中能獲得的最大收益。dp[u][1] 表示偷 u 時…
2. 遞推公式 (通過后序遍歷/DFS實現):
  - 不偷 u (dp[u][0]): 那么它的左孩子 l 和右孩子 r 都可以偷或不偷，取兩者最大值即可。
    
    dp[u][0] = max(dp[l][0], dp[l][1]) + max(dp[r][0], dp[r][1])
  - 偷 u (dp[u][1]): 那么它的左右孩子都不能偷。
    
    dp[u][1] = u->val + dp[l][0] + dp[r][0]
3. 初始化: 遞歸到葉子節點時，dp[leaf][0] = 0, dp[leaf][1] = leaf->val。
4. 遍歷順序: 使用深度優先搜索（DFS），在回溯時（即后序遍歷）進行狀態轉移。
5. 最終解: 對于根節點 root，答案是 max(dp[root][0], dp[root][1])。