数据结构与算法再探（六）动态规划

目录

动态规划 (Dynamic Programming, DP)

动态规划的基本思想

动态规划的核心概念

动态规划的实现步骤

动态规划实例

1、爬楼梯

c++ 递归（超时）需要使用记忆化递归

循环

2、打家劫舍

3、最小路径和

4、完全平方数

5、最长公共子序列

6、0-1背包问题

总结

---

动态规划 (Dynamic Programming, DP)

释义：动态规划是一种解决复杂问题的优化方法，通过将大问题拆解成小问题，逐步解决小问题，最终得到大问题的解。它通常用于求解具有最优子结构和重构子问题的优化问题。C++中的动态规划算法应用广泛，尤其是在最短路径、背包问题、最长公共子序列、矩阵链乘法等领域。

动态规划的基本思想

动态规划方法通过建立状态转移方程（recurrence relation）来表示问题的子问题之间的关系。每个子问题的解只计算一次，然后保存起来避免重复计算，从而达到减少计算量的目的。常见的动态规划问题通常可以通过两种方式实现：自顶向下的递归（带记忆化）和自底向上的迭代。

动态规划的核心概念

最优子结构	问题的最优解可以通过子问题的最优解得到。换句话说问题的最优解包含了子问题的最优解
重叠子问题	问题可以被分解成多个子问题，且这些子问题在计算过程中会被多次求解。
状态转移方程	动态规划的核心是通过状态转移方程将大问题分解为小问题，进而通过小问题的解推导出大问题的解

动态规划的实现步骤

定义状态	首先定义子问题的状态。通常状态的定义取决于问题的具体性质。例如，在最短路径问题中，可以定义状态为当前节点到起点的最短路径长度
初始化状态	为状态的初值赋值。通常，某些边界条件会初始化为已知值。
状态转移方程	根据问题的性质，推导出状态转移方程，描述如何从当前状态推导到下一个状态
计算最优解	根据状态转移方程，从最简单的子问题开始逐步计算，直到得到最终问题的解
结果回溯（如果需要）	：如果问题要求返回具体的解路径（例如路径、序列等），则需要在求解过程中保存路径信息，最后回溯得到结果

动态规划实例

1、爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

状态定义：dp[i]表示爬到第 i 阶楼梯的不同方法数。

状态转移方程：dp[i] =dp[i-1]+dp[i-2]，即爬到第 i 阶楼梯可以从第 i-1 阶或第 i-2 阶跳跃过来。

为什么 d[i] = d[i-1] + d[i-2] 不会重复包含 d[i-2]？
在动态规划中，d[i] 表示到达第 i 阶楼梯的总方法数。当计算 d[i] 时，d[i-1] 和 d[i-2] 分别表示到达第 i-1 阶和第 i-2 阶楼梯的方法数。这两个数并没有交叉或重复计算的部分，它们分别独立表示从不同阶梯出发的跳跃方式。更具体的解释：d[i-1] 代表的是从第 i-1 阶楼梯跳一步到达第 i 阶楼梯的方法数。d[i-2] 代表的是从第 i-2 阶楼梯跳两步到达第 i 阶楼梯的方法数。
这两个值分别代表不同的跳跃方式：从 i-1 到 i 是一次跳跃，跳跃的过程中，不需要考虑 i-2。
从 i-2 到 i 是两次跳跃，这一步也不会再次涉及到 i-1。
因此，d[i-1] 和 d[i-2] 并没有重叠，它们分别计算的是不同的路径，最终的 d[i] = d[i-1] + d[i-2] 是将这两条路径相加，得到的总方法数。

c++ 递归（超时）需要使用记忆化递归

class Solution {
public:int climbStairs(int n) {if(n<=2) return n;return climbStairs(n-1)+climbStairs(n-2);}
};//记录搜素值
vector<int> res;
int dfs(int i){if(i<=1){return 1;}if(res[i]){return res[i];}return res[i]=dfs(i-1)+dfs(i-2);
}

循环

    int climbStairs(int n) {if (n <= 2)return n;vector<int> dp(n + 1, 1);for (int i = 2; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}//空间优化int climbStairs(int n) {if (n <= 2)return n;int pre2 = 1, pre1 = 2, cur;for (int i = 2; i < n; ++i) {cur = pre1 + pre2;pre2 = pre1;pre1 = cur;}return cur;}

2、打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

设 dp[i] 表示偷窃前 i 家房子时的最大金额。显然，对于每个房子，存在两个选择：偷窃第 i 家房子：如果你偷窃第 i 家房子，那么你不能偷窃第 i-1 家房子，因此最大金额是 dp[i-2] + nums[i]，其中 nums[i] 表示第 i 家房子的金额。
不偷窃第 i 家房子：那么最大金额就是 dp[i-1]，即偷窃前 i-1 家房子时的最大金额。因此，递推关系式为：dp[i]=max(dp[i−1],dp[i−2]+nums[i])其中，dp[0] 为偷窃第一家房子的金额，dp[1] 为偷窃前两家房子时的最大金额。

状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始状态：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。

  int rob(vector<int>& nums) {int n=nums.size();vector<int> dp(n,0);if(n==1){return nums[0];}dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<n;++i){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[n-1];}
//空间优化int rob(vector<int>& nums) {int n=nums.size();//vector<int> dp(n,0);if(n==1){return nums[0];}auto pre=0;auto cur=0;int res=0;for(int i=0;i<n;++i){res=max(cur,pre+nums[i]);pre=cur;cur=res;}return res;}

3、最小路径和

64. 最小路径和 - 力扣（LeetCode）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

状态定义：用 dp[i][j] 表示到达位置 (i, j) 的最小路径和。
状态转移：从上方到达 (i, j) 的路径和为 dp[i-1][j] + grid[i][j]。从左方到达 (i, j) 的路径和为 dp[i][j-1] + grid[i][j]。因此，状态转移方程为：dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]；其中，dp[i-1][j] 和 dp[i][j-1] 分别表示到达上方和左方的最小路径和。

初始状态：dp[0][0] = grid[0][0]，即起点的值。第一行和第一列的值需要单独处理，因为它们只能从一个方向到达：第一行：dp[0][j] = dp[0][j-1] + grid[0][j]；第一列：dp[i][0] = dp[i-1][0] + grid[i][0]
返回结果：最终的结果为 dp[m-1][n-1]，即到达右下角的最小路径和。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size();int n=grid[0].size();vector<vector<int>> dp(m,vector<int>(n,0));for(int i=0;i<m;++i){for(int j=0;j<n;++j){if(i==0&&j==0){dp[i][j]=grid[i][j];}else if(i==0){dp[i][j]=dp[i][j-1]+grid[i][j];}else if(j==0){dp[i][j]=dp[i-1][j]+grid[i][j];}else{dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}}return dp[m-1][n-1];}
};

4、完全平方数

279. 完全平方数 - 力扣（LeetCode）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

状态定义：用 dp[i] 表示和为 i 的最小完全平方数的数量。
状态转移：对于每个 i，我们可以尝试用每个小于等于 i 的完全平方数 j*j 来更新 dp[i]：dp[i]=min(dp[i],dp[i−j∗j]+1), 其中 j 是从 1 到 \sqrt{i} 的整数(位置 i 只依赖 i - j*j 的位置，如 i - 1、 i - 4、 i - 9 等等，才能满足完全平方分割的条件)。
初始状态：dp[0] = 0，表示和为 0 时不需要任何数。

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,INT_MAX);dp[0]=0;for(int i=1;i<=n;++i){for(int j=1;j*j<=i;++j){dp[i]=min(dp[i],dp[i-j*j]+1);}}return dp[n];}
};

5、最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

状态定义：用 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。
状态转移：如果 text1[i-1] == text2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符相等时，公共子序列长度加一。如果 text1[i-1] != text2[j-1]，那么 dp[i][j] = \max(dp[i-1][j], dp[i][j-1])，表示当前字符不相等时，最长公共子序列的长度为去掉当前字符后的最大值。
初始状态：dp[0][j] = 0 和 dp[i][0] = 0，表示任意一个字符串为空时，公共子序列长度为 0。
返回结果：最终的结果为 dp[m][n]，其中 m 和 n 分别是 text1 和 text2 的长度。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.length(), n = text2.length();vector<vector<int>> dp(m + 1, 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] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}
};

6、0-1背包问题

有 n 个物品，每个物品 i 有一个重量 weights[i] 和一个价值 values[i]。背包的最大容量为 W。需要找到一个选择方案，使得所选物品的总重量不超过 W，并且总价值最大。动态规划的思路
状态定义：用 dp[i][j] 表示前 i 个物品中，能够放入容量为 j 的背包的最大价值。
状态转移：如果不选择第 i 个物品，最大价值为 dp[i-1][j]。如果选择第 i 个物品，最大价值为 values[i-1] + dp[i-1][j-weights[i-1]]（前提是 j 大于等于 weights[i-1]）。
因此，状态转移方程为：dp[i][j]=max(dp[i−1][j],values[i−1]+dp[i−1][j−weights[i−1]])if j≥weights[i−1]初始状态：dp[0][j] = 0，表示没有物品时，最大价值为 0。返回结果：最终的结果为 dp[n][W]，即使用所有物品时，背包容量为 W 的最大价值。

int knapsack(vector<int> weights, vector<int> values, int N, int W)
{vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));for (int i = 1; i <= N; ++i){int w = weights[i - 1], v = values[i - 1];for (int j = 1; j <= W; ++j){if (j >= w){dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);}else{dp[i][j] = dp[i - 1][j];}}}return dp[N][W];
}

总结

动态规划是一种强大的方法，可以解决很多最优化问题。其核心思想是将问题拆解为子问题，通过记忆化或迭代的方式避免重复计算，从而提高效率。在C++中，动态规划的实现通常涉及状态定义、状态转移方程的推导以及最终解的计算。通过具体的算法问题（如背包问题、最长公共子序列、爬楼梯问题等）来理解和应用动态规划，可以帮助解决复杂的优化问题。