广州制作网站公司电话,外贸联系网站,好用的视频播放器app,天津医疗行业网站建设目录 动态规划 (Dynamic Programming, DP)
动态规划的基本思想
动态规划的核心概念
动态规划的实现步骤
动态规划实例
1、爬楼梯
c 递归#xff08;超时#xff09;需要使用记忆化递归
循环
2、打家劫舍
3、最小路径和
4、完全平方数
5、最长公共子序列
6、0-1背…目录 动态规划 (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(n2) return n;return climbStairs(n-1)climbStairs(n-2);}
};//记录搜素值
vectorint res;
int dfs(int i){if(i1){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;vectorint 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(vectorint nums) {int nnums.size();vectorint dp(n,0);if(n1){return nums[0];}dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(int i2;in;i){dp[i]max(dp[i-1],dp[i-2]nums[i]);}return dp[n-1];}
//空间优化int rob(vectorint nums) {int nnums.size();//vectorint dp(n,0);if(n1){return nums[0];}auto pre0;auto cur0;int res0;for(int i0;in;i){resmax(cur,prenums[i]);precur;curres;}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(vectorvectorint grid) {int mgrid.size();int ngrid[0].size();vectorvectorint dp(m,vectorint(n,0));for(int i0;im;i){for(int j0;jn;j){if(i0j0){dp[i][j]grid[i][j];}else if(i0){dp[i][j]dp[i][j-1]grid[i][j];}else if(j0){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) {vectorint dp(n1,INT_MAX);dp[0]0;for(int i1;in;i){for(int j1;j*ji;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();vectorvectorint dp(m 1, vectorint(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(vectorint weights, vectorint values, int N, int W)
{vectorvectorint dp(N 1, vectorint(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中动态规划的实现通常涉及状态定义、状态转移方程的推导以及最终解的计算。通过具体的算法问题如背包问题、最长公共子序列、爬楼梯问题等来理解和应用动态规划可以帮助解决复杂的优化问题。
