動態規劃：從入門到精通

? ? ? ?本文全章節一共一萬七千多字，詳細介紹動態規劃基礎與進階技巧，全篇以代碼為主，認真讀完理解，你對動態規劃的理解一定會有一個質的飛躍。

一、動態規劃簡介:? ? ? ??

? ? ? ?動態規劃（Dynamic Programming，簡稱DP）?是一種通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。它的核心思想是：將復雜問題分解成子問題，保存子問題的解，避免重復計算。

動態規劃本質上是一種用空間換時間的算法思想：

  • 時間優化：避免重復計算相同的子問題
  • 空間代價：需要額外的存儲空間來保存子問題的解

?動態規劃 vs 其他算法思想

算法思想特點適用場景時間復雜度
暴力遞歸直觀，但有重復計算小規模問題指數級
分治算法分解獨立子問題子問題無重疊通常O(nlogn)
貪心算法局部最優選擇具有貪心選擇性質通常O(n)或O(nlogn)
動態規劃保存子問題解有重疊子問題和最優子結構通常O(n2)或O(n3)

動態規劃的適用條件,動態規劃能夠解決的問題必須具備以下兩個特征:

1.1 最優子結構（Optimal Substructure）

問題的最優解包含其子問題的最優解。

// 示例：最短路徑問題
// 如果A到C的最短路徑是A->B->C，那么B到C的路徑也必須是B到C的最短路徑

1.2? 重疊子問題（Overlapping Subproblems）

在用遞歸算法自頂向下求解時，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次。

// 斐波那契數列的遞歸實現中，f(n-1)和f(n-2)會被重復計算
int fibonacci(int n) {if (n <= 1) return n;return fibonacci(n-1) + fibonacci(n-2); // 大量重復計算
}

1.3? 動態規劃的設計步驟:

步驟1：狀態定義

確定用什么變量來表示子問題的解。

步驟2：狀態轉移方程

找出狀態之間的遞推關系。

步驟3：初始條件和邊界處理

確定初始狀態的值。

步驟4：確定計算順序

確保計算每個狀態時，所依賴的狀態都已經計算出來。

二、經典入門案例

案例1：斐波那契數列

問題描述：計算斐波那契數列的第n項，其中F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

方法1：暴力遞歸（指數時間復雜度）

#include <iostream>
#include <chrono>// 暴力遞歸實現（效率極低）
long long fibonacciRecursive(int n) {if (n <= 1) return n;return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

時間復雜度：O(2^n)
空間復雜度：O(n)（遞歸棧空間）

方法2：自頂向下的記憶化搜索

#include <vector>
#include <unordered_map>class FibonacciMemo {
private:std::unordered_map<int, long long> memo;public:long long fibonacci(int n) {// 基礎情況if (n <= 1) return n;// 檢查是否已經計算過if (memo.find(n) != memo.end()) {return memo[n];}// 計算并存儲結果memo[n] = fibonacci(n - 1) + fibonacci(n - 2);return memo[n];}
};

時間復雜度：O(n)
空間復雜度：O(n)

方法3：自底向上的動態規劃

class FibonacciDP {
public:// 使用數組存儲long long fibonacciArray(int n) {if (n <= 1) return n;std::vector<long long> dp(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];}// 空間優化版本long long fibonacciOptimized(int n) {if (n <= 1) return n;long long prev2 = 0, prev1 = 1;long long current;for (int i = 2; i <= n; i++) {current = prev1 + prev2;prev2 = prev1;prev1 = current;}return current;}
};

時間復雜度：O(n)
空間復雜度：O(1)

案例2：爬樓梯問題

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

分析過程：

  1. 狀態定義：dp[i]?表示爬到第i級臺階的方法數
  2. 狀態轉移方程：dp[i] = dp[i-1] + dp[i-2]
    • 要到達第i級臺階，可以從第i-1級臺階爬1步，或從第i-2級臺階爬2步
  3. 初始條件：dp[1] = 1,?dp[2] = 2

代碼實現：

#include <iostream>
#include <vector>class ClimbingStairs {
public:// 基礎DP版本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];}// 空間優化版本int climbStairsOptimized(int n) {if (n <= 2) return n;int prev2 = 1, prev1 = 2;int current;for (int i = 3; i <= n; i++) {current = prev1 + prev2;prev2 = prev1;prev1 = current;}return current;}// 擴展版本：每次可以爬1到k個臺階int climbStairsK(int n, int k) {std::vector<int> dp(n + 1, 0);dp[0] = 1; // 0級臺階有1種方法（不爬）for (int i = 1; i <= n; i++) {for (int j = 1; j <= k && j <= i; j++) {dp[i] += dp[i - j];}}return dp[n];}
};

案例3：背包問題系列

背包問題是動態規劃的經典應用，我們來看最重要的幾種類型。

0-1背包問題

問題描述：給定n個物品，每個物品有重量weight[i]和價值value[i]。背包容量為W，每個物品只能取一次，求背包能裝入物品的最大價值。

狀態定義與轉移：

  • 狀態定義：dp[i][w]?表示前i個物品，背包容量為w時的最大價值
  • 狀態轉移方程：
    • 不選第i個物品：dp[i][w] = dp[i-1][w]
    • 選第i個物品：dp[i][w] = dp[i-1][w-weight[i]] + value[i]（前提是w >= weight[i]）
    • dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

代碼實現

#include <iostream>
#include <vector>
#include <algorithm>class Knapsack01 {
public:// 二維DP實現int knapsack2D(std::vector<int>& weights, std::vector<int>& values, int capacity) {int n = weights.size();// dp[i][w] 表示前i個物品，容量為w的最大價值std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {// 不選擇第i個物品dp[i][w] = dp[i - 1][w];// 如果能選擇第i個物品if (w >= weights[i - 1]) {dp[i][w] = std::max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);}}}return dp[n][capacity];}// 一維DP實現（空間優化）int knapsack1D(std::vector<int>& weights, std::vector<int>& values, int capacity) {std::vector<int> dp(capacity + 1, 0);for (int i = 0; i < weights.size(); i++) {// 從后往前遍歷，避免重復使用同一個物品for (int w = capacity; w >= weights[i]; w--) {dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);}}return dp[capacity];}// 輸出具體的選擇方案std::vector<int> knapsackSolution(std::vector<int>& weights, std::vector<int>& values, int capacity) {int n = weights.size();std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));// 填充DP表for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {dp[i][w] = dp[i - 1][w];if (w >= weights[i - 1]) {dp[i][w] = std::max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);}}}// 回溯找出具體選擇的物品std::vector<int> selected;int w = capacity;for (int i = n; i > 0; i--) {if (dp[i][w] != dp[i - 1][w]) {selected.push_back(i - 1); // 選擇了第i-1個物品（0-indexed）w -= weights[i - 1];}}std::reverse(selected.begin(), selected.end());return selected;}
};

完全背包問題

問題描述：與0-1背包類似，但每個物品可以選擇無限次。

class KnapsackComplete {
public:int completeKnapsack(std::vector<int>& weights, std::vector<int>& values, int capacity) {std::vector<int> dp(capacity + 1, 0);for (int i = 0; i < weights.size(); i++) {// 從前往后遍歷，允許重復使用同一個物品for (int w = weights[i]; w <= capacity; w++) {dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);}}return dp[capacity];}
};

案例四：序列DP問題

最長遞增子序列（LIS）

問題描述：給定一個數組，找到其中最長的嚴格遞增子序列的長度。

#include <vector>
#include <algorithm>
#include <iostream>class LIS {
public:// O(n2) DP解法int lengthOfLIS_DP(std::vector<int>& nums) {if (nums.empty()) return 0;int n = nums.size();std::vector<int> dp(n, 1); // dp[i]表示以nums[i]結尾的最長遞增子序列長度int maxLength = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = std::max(dp[i], dp[j] + 1);}}maxLength = std::max(maxLength, dp[i]);}return maxLength;}// 獲取具體的LIS序列std::vector<int> findLIS(std::vector<int>& nums) {if (nums.empty()) return {};int n = nums.size();std::vector<int> dp(n, 1);std::vector<int> parent(n, -1); // 記錄前驅元素的索引int maxLength = 1;int maxIndex = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;parent[i] = j;}}if (dp[i] > maxLength) {maxLength = dp[i];maxIndex = i;}}// 構造LIS序列std::vector<int> lis;int current = maxIndex;while (current != -1) {lis.push_back(nums[current]);current = parent[current];}std::reverse(lis.begin(), lis.end());return lis;}// O(nlogn) 二分搜索解法int lengthOfLIS_Binary(std::vector<int>& nums) {if (nums.empty()) return 0;std::vector<int> tails; // tails[i] 表示長度為i+1的遞增子序列的最小尾部元素for (int num : nums) {auto it = std::lower_bound(tails.begin(), tails.end(), num);if (it == tails.end()) {tails.push_back(num);} else {*it = num;}}return tails.size();}
};

最長公共子序列（LCS）

問題描述：給定兩個字符串，找到它們的最長公共子序列的長度。

class LCS {
public:int longestCommonSubsequence(std::string text1, std::string text2) {int m = text1.length(), n = text2.length();// dp[i][j] 表示text1[0..i-1]和text2[0..j-1]的LCS長度std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}// 獲取具體的LCS字符串std::string findLCS(std::string text1, std::string text2) {int m = text1.length(), n = text2.length();std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));// 填充DP表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);}}}// 回溯構造LCSstd::string lcs;int i = m, j = n;while (i > 0 && j > 0) {if (text1[i - 1] == text2[j - 1]) {lcs = text1[i - 1] + lcs;i--;j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {i--;} else {j--;}}return lcs;}
};

案例五：路徑問題

最小路徑和

問題描述：給定一個包含非負整數的m×n網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

class PathSum {
public:int minPathSum(std::vector<std::vector<int>>& grid) {if (grid.empty() || grid[0].empty()) return 0;int m = grid.size(), n = grid[0].size();std::vector<std::vector<int>> dp(m, std::vector<int>(n));// 初始化第一個格子dp[0][0] = grid[0][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++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 填充其余位置for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}return dp[m - 1][n - 1];}// 空間優化版本int minPathSumOptimized(std::vector<std::vector<int>>& grid) {if (grid.empty() || grid[0].empty()) return 0;int m = grid.size(), n = grid[0].size();std::vector<int> dp(n);dp[0] = grid[0][0];for (int j = 1; j < n; j++) {dp[j] = dp[j - 1] + grid[0][j];}for (int i = 1; i < m; i++) {dp[0] += grid[i][0];for (int j = 1; j < n; j++) {dp[j] = std::min(dp[j], dp[j - 1]) + grid[i][j];}}return dp[n - 1];}// 輸出具體路徑std::vector<std::pair<int, int>> findMinPath(std::vector<std::vector<int>>& grid) {if (grid.empty() || grid[0].empty()) return {};int m = grid.size(), n = grid[0].size();std::vector<std::vector<int>> dp(m, std::vector<int>(n));// 計算DP表（同上）dp[0][0] = grid[0][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++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}// 回溯找路徑std::vector<std::pair<int, int>> path;int i = m - 1, j = n - 1;while (i > 0 || j > 0) {path.push_back({i, j});if (i == 0) {j--;} else if (j == 0) {i--;} else {if (dp[i - 1][j] < dp[i][j - 1]) {i--;} else {j--;}}}path.push_back({0, 0});std::reverse(path.begin(), path.end());return path;}
};

案例六：區間DP

區間DP是在區間上進行動態規劃，通常用來解決關于區間的最優化問題。

矩陣鏈乘法

問題描述：給定n個矩陣的維度，求這些矩陣相乘時的最少標量乘法次數。

class MatrixChainMultiplication {
public:int matrixChainOrder(std::vector<int>& dims) {int n = dims.size() - 1; // n個矩陣// dp[i][j] 表示矩陣i到矩陣j相乘的最少乘法次數std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));// l是鏈的長度，從2開始for (int l = 2; l <= n; l++) {for (int i = 0; i <= n - l; i++) {int j = i + l - 1;dp[i][j] = INT_MAX;// 嘗試所有可能的分割點kfor (int k = i; k < j; k++) {int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];dp[i][j] = std::min(dp[i][j], cost);}}}return dp[0][n - 1];}// 輸出最優括號化方案void printOptimalParens(std::vector<std::vector<int>>& s, int i, int j, std::string& result) {if (i == j) {result += "M" + std::to_string(i);} else {result += "(";printOptimalParens(s, i, s[i][j], result);printOptimalParens(s, s[i][j] + 1, j, result);result += ")";}}std::string getOptimalParentheses(std::vector<int>& dims) {int n = dims.size() - 1;std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));std::vector<std::vector<int>> s(n, std::vector<int>(n, 0)); // 記錄分割點for (int l = 2; l <= n; l++) {for (int i = 0; i <= n - l; i++) {int j = i + l - 1;dp[i][j] = INT_MAX;for (int k = i; k < j; k++) {int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];if (cost < dp[i][j]) {dp[i][j] = cost;s[i][j] = k;}}}}std::string result;printOptimalParens(s, 0, n - 1, result);return result;}
};

?案例七：樹形DP

樹形DP是在樹結構上進行的動態規劃。

二叉樹的最大路徑和

問題描述：給定一個二叉樹，找到任意兩個節點間路徑上數值和的最大值。

#include <algorithm>
#include <climits>struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class TreeDP {
private:int maxSum = INT_MIN;// 返回以當前節點為起點的最大路徑和（只能向下）int maxPathDown(TreeNode* node) {if (!node) return 0;// 遞歸計算左右子樹的最大貢獻值// 如果子樹路徑和為負，則不選擇該路徑（用0代替）int leftMax = std::max(maxPathDown(node->left), 0);int rightMax = std::max(maxPathDown(node->right), 0);// 當前節點的最大路徑和（可能經過當前節點連接左右子樹）int currentMax = node->val + leftMax + rightMax;// 更新全局最大值maxSum = std::max(maxSum, currentMax);// 返回當前節點向上的最大貢獻值（只能選擇一邊）return node->val + std::max(leftMax, rightMax);}public:int maxPathSum(TreeNode* root) {maxSum = INT_MIN;maxPathDown(root);return maxSum;}
};

打家劫舍III（樹上版本）

問題描述：小偷在二叉樹形狀的房屋中偷盜，不能偷相鄰的房屋（父子節點不能同時偷）。

class HouseRobberTree {
public:// 返回一個pair：{不偷當前節點的最大收益, 偷當前節點的最大收益}std::pair<int, int> robHelper(TreeNode* node) {if (!node) return {0, 0};auto left = robHelper(node->left);auto right = robHelper(node->right);// 不偷當前節點：左右子樹可偷可不偷，取最大值int notRob = std::max(left.first, left.second) + std::max(right.first, right.second);// 偷當前節點：左右子樹都不能偷int rob = node->val + left.first + right.first;return {notRob, rob};}int rob(TreeNode* root) {auto result = robHelper(root);return std::max(result.first, result.second);}
};

?案例八：狀態壓縮DP

當狀態數量較少時，可以用位運算來壓縮狀態，提高效率。

旅行商問題（TSP）

問題描述：給定n個城市和它們之間的距離，找到訪問所有城市恰好一次并回到起點的最短路徑。

class TSP {
public:int tsp(std::vector<std::vector<int>>& dist) {int n = dist.size();int fullMask = (1 << n) - 1; // 所有城市都訪問過的狀態// dp[mask][i] 表示當前訪問過的城市集合為mask，當前在城市i的最小距離std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX));// 從城市0開始dp[1][0] = 0; // 狀態1表示只訪問了城市0for (int mask = 1; mask < (1 << n); mask++) {for (int u = 0; u < n; u++) {if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;// 嘗試從城市u轉移到城市vfor (int v = 0; v < n; v++) {if (mask & (1 << v)) continue; // 城市v已經訪問過int newMask = mask | (1 << v);dp[newMask][v] = std::min(dp[newMask][v], dp[mask][u] + dist[u][v]);}}}// 找到訪問所有城市后回到起點的最小距離int result = INT_MAX;for (int i = 1; i < n; i++) {if (dp[fullMask][i] != INT_MAX) {result = std::min(result, dp[fullMask][i] + dist[i][0]);}}return result;}// 輸出具體路徑std::vector<int> getTSPPath(std::vector<std::vector<int>>& dist) {int n = dist.size();int fullMask = (1 << n) - 1;std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX));std::vector<std::vector<int>> parent(1 << n, std::vector<int>(n, -1));dp[1][0] = 0;for (int mask = 1; mask < (1 << n); mask++) {for (int u = 0; u < n; u++) {if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;for (int v = 0; v < n; v++) {if (mask & (1 << v)) continue;int newMask = mask | (1 << v);int newDist = dp[mask][u] + dist[u][v];if (newDist < dp[newMask][v]) {dp[newMask][v] = newDist;parent[newMask][v] = u;}}}}// 找到最優的結束城市int minDist = INT_MAX;int lastCity = -1;for (int i = 1; i < n; i++) {if (dp[fullMask][i] + dist[i][0] < minDist) {minDist = dp[fullMask][i] + dist[i][0];lastCity = i;}}// 重構路徑std::vector<int> path;int currentMask = fullMask;int currentCity = lastCity;while (currentCity != -1) {path.push_back(currentCity);int prevCity = parent[currentMask][currentCity];currentMask ^= (1 << currentCity);currentCity = prevCity;}std::reverse(path.begin(), path.end());path.push_back(0); // 回到起點return path;}
};

?三、DP優化技巧

1. 滾動數組優化空間

當DP狀態只依賴于前一個或前幾個狀態時，可以使用滾動數組節省空間。

// 示例：背包問題的空間優化
class SpaceOptimization {
public:// 原始二維DPint knapsack2D(std::vector<int>& weights, std::vector<int>& values, int capacity) {int n = weights.size();std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {dp[i][w] = dp[i-1][w];if (w >= weights[i-1]) {dp[i][w] = std::max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);}}}return dp[n][capacity];}// 空間優化后的一維DPint knapsack1D(std::vector<int>& weights, std::vector<int>& values, int capacity) {std::vector<int> dp(capacity + 1, 0);for (int i = 0; i < weights.size(); i++) {for (int w = capacity; w >= weights[i]; w--) {dp[w] = std::max(dp[w], dp[w-weights[i]] + values[i]);}}return dp[capacity];}
};

2. 單調隊列優化

在某些DP轉移中，可以使用單調隊列來優化時間復雜度。

#include <deque>class MonotonicQueueOptimization {
public:// 滑動窗口最大值的DP應用std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {std::deque<int> dq; // 存儲數組下標std::vector<int> result;for (int i = 0; i < nums.size(); i++) {// 移除超出窗口范圍的元素while (!dq.empty() && dq.front() <= i - k) {dq.pop_front();}// 維護單調遞減隊列while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}dq.push_back(i);// 當窗口大小達到k時，記錄最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;}
};

3. 矩陣快速冪優化

對于線性遞推關系，可以使用矩陣快速冪將時間復雜度從O(n)降到O(logn)。

class MatrixFastPower {
private:using Matrix = std::vector<std::vector<long long>>;Matrix multiply(const Matrix& A, const Matrix& B) {int n = A.size();Matrix C(n, std::vector<long long>(n, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {C[i][j] += A[i][k] * B[k][j];}}}return C;}Matrix matrixPower(Matrix base, long long exp) {int n = base.size();Matrix result(n, std::vector<long long>(n, 0));// 初始化為單位矩陣for (int i = 0; i < n; i++) {result[i][i] = 1;}while (exp > 0) {if (exp & 1) {result = multiply(result, base);}base = multiply(base, base);exp >>= 1;}return result;}public:// 使用矩陣快速冪計算斐波那契數列long long fibonacciMatrix(long long n) {if (n <= 1) return n;// 轉移矩陣: [[1,1],[1,0]]Matrix base = {{1, 1}, {1, 0}};Matrix result = matrixPower(base, n - 1);// F(n) = result[0][0] * F(1) + result[0][1] * F(0)//      = result[0][0] * 1 + result[0][1] * 0//      = result[0][0]return result[0][0];}
};

四、綜合練習題

練習1：最大子數組和（Kadane算法）

class MaxSubarray {
public:int maxSubArray(std::vector<int>& nums) {int maxSum = nums[0];int currentSum = nums[0];for (int i = 1; i < nums.size(); i++) {// 要么繼續之前的子數組，要么重新開始currentSum = std::max(nums[i], currentSum + nums[i]);maxSum = std::max(maxSum, currentSum);}return maxSum;}// 返回具體的最大子數組std::vector<int> findMaxSubArray(std::vector<int>& nums) {int maxSum = nums[0];int currentSum = nums[0];int start = 0, end = 0, tempStart = 0;for (int i = 1; i < nums.size(); i++) {if (currentSum < 0) {currentSum = nums[i];tempStart = i;} else {currentSum += nums[i];}if (currentSum > maxSum) {maxSum = currentSum;start = tempStart;end = i;}}return std::vector<int>(nums.begin() + start, nums.begin() + end + 1);}
};

練習2：編輯距離

class EditDistance {
public:int minDistance(std::string word1, std::string word2) {int m = word1.length(), n = word2.length();// dp[i][j] 表示word1[0..i-1]轉換為word2[0..j-1]的最小操作數std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));// 初始化邊界條件for (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1[i-1] == word2[j-1]) {dp[i][j] = dp[i-1][j-1]; // 不需要操作} else {dp[i][j] = 1 + std::min({dp[i-1][j],    // 刪除dp[i][j-1],    // 插入dp[i-1][j-1]   // 替換});}}}return dp[m][n];}// 輸出具體的編輯操作序列std::vector<std::string> getEditOperations(std::string word1, std::string word2) {int m = word1.length(), n = word2.length();std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));// 填充DP表（同上）for (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1[i-1] == word2[j-1]) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = 1 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});}}}// 回溯操作序列std::vector<std::string> operations;int i = m, j = n;while (i > 0 || j > 0) {if (i > 0 && j > 0 && word1[i-1] == word2[j-1]) {i--; j--;} else if (i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + 1) {operations.push_back("Replace " + std::string(1, word1[i-1]) + " with " + std::string(1, word2[j-1]));i--; j--;} else if (i > 0 && dp[i][j] == dp[i-1][j] + 1) {operations.push_back("Delete " + std::string(1, word1[i-1]));i--;} else {operations.push_back("Insert " + std::string(1, word2[j-1]));j--;}}std::reverse(operations.begin(), operations.end());return operations;}
};

?總結與進階建議

DP解題模板：

// 通用DP解題模板
class DPTemplate {
public:int solveProblem(/* 輸入參數 */) {// 第1步：確定狀態定義// dp[i][j][...] 的含義是什么？// 第2步：找出狀態轉移方程// dp[i][j] = f(dp[...], dp[...], ...)// 第3步：確定初始條件和邊界// dp的初始值是什么？// 第4步：確定計算順序// 保證計算dp[i][j]時，所依賴的狀態都已計算// 第5步：優化空間復雜度（如果可能）// 使用滾動數組等技巧return 0; // 返回最終答案}
};

DP問題分類總結

類型特征常見問題時間復雜度
線性DP狀態轉移呈線性關系爬樓梯、最大子序列和O(n)
區間DP在區間上進行DP矩陣鏈乘法、回文子串O(n3)
背包DP選擇物品的最優化問題0-1背包、完全背包O(nW)
樹形DP在樹結構上的DP樹的直徑、打家劫舍IIIO(n)
狀態壓縮DP用位運算壓縮狀態TSP、集合覆蓋O(n22?)
數位DP按數位進行的DP統計特定數字個數O(logn)

進階學習路徑

  1. 掌握基礎問題：從斐波那契、爬樓梯開始
  2. 熟練背包問題：0-1背包、完全背包、多重背包
  3. 掌握序列DP：LIS、LCS、編輯距離
  4. 學習區間DP：矩陣鏈乘法、石子合并
  5. 深入樹形DP：樹的直徑、重心分解
  6. 挑戰狀態壓縮：TSP、狀態空間搜索
  7. 學習優化技巧：單調隊列、斜率優化、矩陣快速冪

調試技巧

// DP調試輔助函數
class DPDebugger {
public:template<typename T>void printDP(const std::vector<std::vector<T>>& dp, const std::string& name) {std::cout << "=== " << name << " ===" << std::endl;for (int i = 0; i < dp.size(); i++) {for (int j = 0; j < dp[i].size(); j++) {std::cout << std::setw(6) << dp[i][j] << " ";}std::cout << std::endl;}std::cout << std::endl;}template<typename T>void print1D(const std::vector<T>& arr, const std::string& name) {std::cout << name << ": ";for (const auto& x : arr) {std::cout << x << " ";}std::cout << std::endl;}
};

🏆 最后的話

? ? ? ?動態規劃是算法設計中的一顆明珠，它教會我們如何化繁為簡，化重復為存儲。掌握DP不僅能幫你解決編程競賽中的難題，更重要的是能培養你分解復雜問題的思維能力。

記住DP的精髓：

  • 最優子結構：大問題的最優解包含小問題的最優解
  • 重疊子問題：避免重復計算，用空間換時間
  • 狀態轉移：找出問題內在的遞推關系

多練習，多思考，相信你一定能掌握這個強大的算法思想！

練習建議：每天至少做1-2道不同類型的DP題目，并嘗試優化空間復雜度。熟能生巧，DP的精髓就在于大量的練習和思考。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/93442.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/93442.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/93442.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

八股訓練營 40 天心得：一場結束，也是一場新的開始

八股訓練營 40 天心得：一場結束，也是一場新的開始

八股訓練營 40 天心得&#xff1a;一場結束&#xff0c;也是一場新的開始 感謝卡哥的訓練營組織卡碼筆記&#xff0c;對即將參加秋招的我們幫助了很多&#xff0c;感謝卡哥的開源代碼隨想錄代碼隨想錄 四十天前&#xff0c;我帶著一顆不安卻堅定的心&#xff0c;踏入了這場“…
閱讀更多...
STM32系統定時器（SysTick）詳解：從原理到實戰的精確延時與任務調度

STM32系統定時器（SysTick）詳解：從原理到實戰的精確延時與任務調度

前言&#xff1a;為什么SysTick是嵌入式開發的"瑞士軍刀"&#xff1f; 在STM32開發中&#xff0c;我們經常需要精確的延時功能&#xff08;如毫秒級延時控制LED閃爍&#xff09;或周期性任務調度&#xff08;如定時采集傳感器數據&#xff09;。實現這些功能的方式有…
閱讀更多...
【微信小程序】12、生物認證能力

【微信小程序】12、生物認證能力

1、生物認證 生物認證 是一種基于個體獨特生理或行為特征進行身份驗證的技術,廣泛應用于安全、金融、醫療等領域。 小程序目前暫時只支持指紋識別認證。 2、查詢支持的生物認證方式 獲取本機支持的 SOTER 生物認證方式&#xff0c;文檔 onLoad(options) {wx.checkIsSuppor…
閱讀更多...
高級機器學習

高級機器學習

機器學習常見方法涉及方法&#xff1a;2.半監督學習3.無監督學習4.度量學習5.遷移學習6.多示例多標記學習7.在線學習8.元學習9.聯邦學習10.強化學習11.概率圖模型獨立同分布獨立指的是&#xff0c;樣本集包括訓練集測試集的任意兩個樣本之間都是不相關的。在表示樣本的特征確定…
閱讀更多...
Chrome 提示 “此擴展程序不再受支持”(MacOS/Windows)

Chrome 提示 “此擴展程序不再受支持”(MacOS/Windows)

原因 最新 Chrome 使用 Manifest V3, 并在新版瀏覽器中 停止 V2 支持 處理方法 MacOS 新建一個后綴為 .mobileconfig 的文件, 內容參考 <?xml version"1.0" encoding"UTF-8"?> <!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN&…
閱讀更多...
C++20協程實戰：高效網絡庫、手機終端、多媒體開發開發指南

C++20協程實戰：高效網絡庫、手機終端、多媒體開發開發指南

基于C++協程和事件循環的網絡庫 以下是基于C++協程和事件循環的網絡庫實例，涵蓋常見場景和功能實現。示例基于libuv、Boost.Asio或自定義事件循環，結合C++20協程（如std::coroutine）或其他協程庫（如cppcoro）實現。 基礎TCP服務器 #include <cppcoro/task.hpp> #in…
閱讀更多...
數據庫4.0

數據庫4.0

索引 事務 JDBC~ 目錄 一、MySQL索引 1.0 概述 2.0 相關操作 3.0 注意 4.0 索引背后的原理的理解 二、 事務 1.0 原子性 2.0 隔離性 (1)并發執行 (2) 出現的問題 3.0 使用 三、JDBC編程 1.0 概述 2.0 如何下載驅動包 3.0 jar如何引入到項目之中 4.0 jdbc…
閱讀更多...
HarmonyOS-ArkUI Web控件基礎鋪墊6--TCP協議- 流量控制算法與擁塞控制算法

HarmonyOS-ArkUI Web控件基礎鋪墊6--TCP協議- 流量控制算法與擁塞控制算法

HarmonyOS-ArkUI Web控件基礎鋪墊1-HTTP協議-數據包內容-CSDN博客 HarmonyOS-ArkUI Web控件基礎鋪墊2-DNS解析-CSDN博客 HarmonyOS-ArkUI Web控件基礎鋪墊3--TCP協議- 從規則本質到三次握手-CSDN博客 HarmonyOS-ArkUI Web控件基礎鋪墊4--TCP協議- 斷聯-四次揮手解析-CSDN博客…
閱讀更多...
Dify 從入門到精通（2/100 篇）：Dify 的核心組件 —— 從節點到 RAG 管道

Dify 從入門到精通（2/100 篇）：Dify 的核心組件 —— 從節點到 RAG 管道

Dify 的核心組件&#xff1a;從節點到 RAG 管道 引言 在 Dify 博客系列&#xff1a;從入門到精通&#xff08;100 篇&#xff09; 的第一篇《Dify 究竟是什么&#xff1f;真能開啟低代碼 AI 應用開發的未來&#xff1f;》中&#xff0c;我們全面介紹了 Dify 的定位、核心特點…
閱讀更多...
在線培訓、遠程示教——醫療器械行業的直播解決方案

在線培訓、遠程示教——醫療器械行業的直播解決方案

文章目錄前言一、醫療器械直播應用的兩大核心場景二、直播平臺在醫療場景中的關鍵技術支持點三、典型功能實現原理總結前言 醫療器械行業對“培訓”和“示教”的專業性要求極高&#xff0c;傳統的線下模式常因時間、空間、人員成本等受限而效率低下。而隨著高清低延遲視頻技術…
閱讀更多...
Mqttnet的MqttClientTlsOptions.CertificateValidationHandler詳解

Mqttnet的MqttClientTlsOptions.CertificateValidationHandler詳解

MqttClientTlsOptions.CertificateValidationHandler 是 MQTTnet 庫中用于自定義 TLS 證書驗證邏輯的關鍵回調函數。在 MQTT 客戶端與服務器建立 TLS 連接時&#xff0c;該回調允許你覆蓋默認的證書驗證流程&#xff0c;實現自定義的安全策略。核心作用當 MQTT 客戶端通過 TLS …
閱讀更多...
【圖像噪點消除】——圖像預處理（OpenCV）

【圖像噪點消除】——圖像預處理（OpenCV）

目錄 1 均值濾波 2 方框濾波 3 高斯濾波 4 中值濾波 5 雙邊濾波 6 小結 噪聲&#xff1a;圖像中的一些干擾因素。通常是由于圖像采集設備、傳輸信道等因素造成的&#xff0c;表現為圖像中隨機的亮度。常見的噪聲類型有高斯噪聲和椒鹽噪聲。高斯噪聲是一種分布符合正態分布…
閱讀更多...
Vulnhub napping-1.0.1靶機滲透攻略詳解

Vulnhub napping-1.0.1靶機滲透攻略詳解

一、下載靶機 下載地址&#xff1a;https://download.vulnhub.com/napping/napping-1.0.1.ova 下載好后使用VM打開&#xff0c;將網絡配置模式改為net&#xff0c;防止橋接其他主機干擾&#xff08;橋接Mac地址也可確定主機&#xff09;。 二、發現主機 使用nmap掃描沒有相應…
閱讀更多...
Kubernetes自動擴容方案

Kubernetes自動擴容方案

Kubernetes 自動擴容可以概括為 “三層六類”&#xff1a;層級類型觸發維度官方/社區方案一句話說明Pod 級HPACPU / 內存 / 自定義 / 外部指標內置副本數橫向擴縮&#xff0c;最常用VPACPU / 內存社區組件單 Pod 資源豎向擴縮&#xff0c;不改副本數KEDA任意事件&#xff08;隊…
閱讀更多...
linux命令ps的實際應用

linux命令ps的實際應用

ps&#xff08;Process Status&#xff09;是 ?Linux/Unix 系統中最核心的進程管理工具&#xff0c;用于實時抓取系統進程快照。它直接讀取 /proc 文件系統&#xff0c;不持續監控進程&#xff08;區別于 top&#xff09;&#xff0c;但可通過參數組合實現精準進程診斷。下面從…
閱讀更多...
深入理解C語言：詳解直接插入排序的實現與優化

深入理解C語言：詳解直接插入排序的實現與優化

目錄 引言 一、直接插入排序的相關概念 1.1、基本概念 1.2、直接插入排序過程詳解 二、代碼實現 三、時間復雜度 四、希爾排序 4.1、希爾排序的陳述 4.2、代碼實現 4.3、時間復雜度 結語 引言 在計算機科學的世界里&#xff0c;排序算法是基礎且重要的組成部分。它們…
閱讀更多...
【DRAM存儲器五十五】LPDDR5介紹--command bus training

【DRAM存儲器五十五】LPDDR5介紹--command bus training

??個人主頁：highman110 ??作者簡介：一名硬件工程師，持續學習，不斷記錄，保持思考，輸出干貨內容 參考資料：《某LPDDR5數據手冊》 、《JESD209-5A》 在為高頻或中頻操作啟用ODT之前，必須對L
閱讀更多...
一道曾經百度面試題

一道曾經百度面試題

&#x1f680;個人主頁&#xff1a;BabyZZの秘密日記 &#x1f4d6;收入專欄&#xff1a;C語言 &#x1f30d;文章目入1. 題目重現2. 大小端到底在比什么&#xff1f;3. 解法一&#xff1a;聯合體&#xff08;union&#xff09;為什么一行就夠&#xff1f;使用示例4. 解法二&am…
閱讀更多...
VIKOR（Multi-criteria Optimization and Compromise Solution）簡介與簡單示例

VIKOR（Multi-criteria Optimization and Compromise Solution）簡介與簡單示例

前言 提醒&#xff1a; 文章內容為方便作者自己后日復習與查閱而進行的書寫與發布&#xff0c;其中引用內容都會使用鏈接表明出處&#xff08;如有侵權問題&#xff0c;請及時聯系&#xff09;。 其中內容多為一次書寫&#xff0c;缺少檢查與訂正&#xff0c;如有問題或其他拓展…
閱讀更多...
【算法訓練營Day18】二叉樹part8

【算法訓練營Day18】二叉樹part8

文章目錄修剪二叉搜索樹將有序數組轉換為二叉搜索樹把二叉搜索樹轉換為累加樹修剪二叉搜索樹 題目鏈接&#xff1a;669. 修剪二叉搜索樹 解題邏輯&#xff1a; 因為在刪除的同時要保證相對結構&#xff0c;所以我們不能沿用上一篇文章中的刪除邏輯&#xff0c;新的刪除邏輯為&…
閱讀更多...
最新文章

Copyright @ 2022~2023