动态规划：从入门到精通

       本文全章节一共一万七千多字，详细介绍动态规划基础与进阶技巧，全篇以代码为主，认真读完理解，你对动态规划的理解一定会有一个质的飞跃。

一、动态规划简介:        

       动态规划（Dynamic Programming，简称DP） 是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它的核心思想是：将复杂问题分解成子问题，保存子问题的解，避免重复计算。

动态规划本质上是一种用空间换时间的算法思想：

  • 时间优化：避免重复计算相同的子问题
  • 空间代价：需要额外的存储空间来保存子问题的解

 动态规划 vs 其他算法思想

算法思想特点适用场景时间复杂度
暴力递归直观，但有重复计算小规模问题指数级
分治算法分解独立子问题子问题无重叠通常O(nlogn)
贪心算法局部最优选择具有贪心选择性质通常O(n)或O(nlogn)
动态规划保存子问题解有重叠子问题和最优子结构通常O(n²)或O(n³)

动态规划的适用条件,动态规划能够解决的问题必须具备以下两个特征:

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(n²) 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(n³)
背包DP选择物品的最优化问题0-1背包、完全背包O(nW)
树形DP在树结构上的DP树的直径、打家劫舍IIIO(n)
状态压缩DP用位运算压缩状态TSP、集合覆盖O(n²2ⁿ)
数位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

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈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