从小白开始的动态规划

一、动态规划的核心思想

动态规划（DP）通过拆分问题+记忆化计算解决复杂问题，核心步骤为：

定义状态：用变量（如dp[i]）表示子问题的解
状态转移方程：建立子问题之间的关系式
初始化：确定基础情况的初始值
计算顺序：确定填表方向（自底向上/自顶向下）

二、动态规划解题四部曲

分析问题是否具有重叠子问题和最优子结构
定义明确的状态表示
推导状态转移关系
处理边界条件并实现

三、经典DP问题分类与实战

类型1：记忆化递归（斐波那契数列）

问题：计算第n个斐波那契数
分析：

状态定义：dp[i]表示第i个斐波那契数
转移方程：dp[i] = dp[i-1] + dp[i-2]

int fib(int n) {if(n <= 1) return n;vector<int> 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];
}

类型2：线性DP（爬楼梯）

问题：每次爬1/2阶，到n阶有多少种方法
分析：

状态定义：dp[i]表示到达第i阶的方法数
转移方程：dp[i] = dp[i-1] + dp[i-2]

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

类型3：状态机DP（打家劫舍）

问题：不能偷相邻房屋，求最大收益
分析：

状态定义：dp[i][0]不偷第i家的最大收益，dp[i][1]偷第i家的收益
转移方程：
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]

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

类型4：背包问题（0-1背包）

问题：容量W的背包，物品重量weight[]和价值value[]，求最大价值
分析：

状态定义：dp[i][j]前i个物品装入容量j的背包的最大价值
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

int knapsack(int W, vector<int>& weight, vector<int>& value) {int n = weight.size();vector<vector<int>> dp(n+1, vector<int>(W+1));for(int i=1; i<=n; ++i){for(int j=1; j<=W; ++j){if(j >= weight[i-1]){dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);}else{dp[i][j] = dp[i-1][j];}}}return dp[n][W];
}

类型5：二维路径DP（最小路径和）

问题：m x n网格，从左上到右下的最小路径和
分析：

状态定义：dp[i][j]表示到(i,j)的最小路径和
转移方程：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m, vector<int>(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] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];}}return dp[m-1][n-1];
}

类型6：字符串DP（编辑距离）

问题：将word1转换为word2的最小操作次数（增/删/改）
分析：

状态定义：dp[i][j]表示word1前i个字符转成word2前j个字符的最小步数
转移方程：

if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
elsedp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;

int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();vector<vector<int>> dp(m+1, 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] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;}}}return dp[m][n];
}