宋庄网站建设,哪个网站有激光打标业务做,小程序定制开发深圳,chatgpt 网址专题六#xff1a;动态规划 目录专题六#xff1a;动态规划导读什么是动态规划解决的问题解题步骤动态规划应该如何debug记忆化搜索斐波那契数题目代码题解爬楼梯题目代码题解使用最小花费爬楼梯题目代码题解不同路径题目题解dfsdp凑硬币题目题解dfsdp滑雪题目代码题解汉罗塔…专题六动态规划 目录专题六动态规划导读什么是动态规划解决的问题解题步骤动态规划应该如何debug记忆化搜索斐波那契数题目代码题解爬楼梯题目代码题解使用最小花费爬楼梯题目代码题解不同路径题目题解dfsdp凑硬币题目题解dfsdp滑雪题目代码题解汉罗塔题目题解dfsdp01背包问题题目代码题解摘花生题目代码题解最长上升子序列题目代码题解总结在这里插入图片描述
导读
本专题将讲解最难理解的算法之一动态规划。介绍动态规划的基本概念、算法原理以及应用场景。首先我们将介绍动态规划的定义和特点以及它与递归、贪心算法的区别。接着我们将详细介绍动态规划的解题思路和算法流程包括状态转移方程、边界条件、初始化等概念。最后我们将讨论动态规划在实际问题中的应用包括背包问题、最长公共子序列问题、最短路径问题等。
什么是动态规划
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题于最优子问题使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的.
例如有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])。
但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
解决的问题
动态规划是一种数学方法用于求解决策过程的最优化问题。如果一个问题可以分解成若干个子问题并且子问题之间还有重叠的更小的子问题就可以考虑使用动态规划来解决这个问题。应用动态规划之前要分析能否把大问题分解成小问题分解后的每个小问题也存在最优解。如果将小问题的最优解组合起来能够得到整个问题的最优解那么就可以使用动态规划解决问题。可以应用动态规划求解的问题主要具有以下四个特点
问题是求最优解。 整体问题的最优解依赖于各个子问题的最优解。 大问题分解成若干小问题这些小问题之间还有相互重叠的更小的子问题。 从上往下分析问题从下往上求解问题。
解题步骤
对于动态规划问题我将拆解为如下五步曲这五步都搞清楚了才能说把动态规划真的掌握了
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
分享两张两种解决动态规划的思维导图 动态规划应该如何debug
找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的
做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。
然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。
记忆化搜索
可以理解为实现dp的另一种方法用递归实现本质还是搜索。
记忆化搜索按照自顶向下的顺序每求得一个状态时就把它的解保存下来以后再次遇到这个状态时就不用重复求解了。
记忆化搜索包含两个要素记忆化和搜索。
沿用搜索的一般模式本质还是用递归函数实现。在搜索的过程中将已经得到的解保存起来下次需要时直接用。
斐波那契数
题目
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1
给定 n 请计算 F(n) 。
示例 1
输入 n 2 输出 1 解释 F(2) F(1) F(0) 1 0 1
示例 2
输入 n 3 输出 2 解释 F(3) F(2) F(1) 1 1 2
示例 3
输入 n 4 输出 3 解释 F(4) F(3) F(2) 2 1 3
提示
0 n 30
代码
class Solution {
public:int fib(int n) {if(n2) return n;vectorint dp(n1);dp[0]0;dp[1]1;for(int i2;in;i){dp[i]dp[i-1]dp[i-2];// coutdp[i]endl;}return dp[n];}
};题解
动态规划五部曲 确定dp数组以及下标的含义 dp[i]定义为第i个数的斐波那契值为dp[i] 确定递推公式 状态转移方程dp[i]dp[i-1]dp[i-2] dp数组如何初始化 dp[0]0; dp[1]1; 确定遍历顺序 从前往后循环遍历dp问题一般都是自底向上去思考。
爬楼梯
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入 n 2
输出 2
解释 有两种方法可以爬到楼顶。
1 阶 1 阶2 阶
示例 2
输入 n 3
输出 3
解释 有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶
提示
1 n 45
代码 class Solution {
public:int climbStairs(int n) {if (n 1) return n; // 因为下面直接对dp[2]操作了防止空指针vectorint dp(n 1);dp[1] 1;dp[2] 2;for (int i 3; i n; i) { // 注意i是从3开始的dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};题解
爬到第一层楼梯有一种方法爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。
确定dp数组以及下标的含义
dp[i] 爬到第i层楼梯有dp[i]种方法 2 . 确定递推公式
如果可以推出dp[i]呢
从dp[i]的定义可以看出dp[i] 可以有两个方向推出来。
首先是dp[i - 1]上i-1层楼梯有dp[i - 1]种方法那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]上i-2层楼梯有dp[i - 2]种方法那么再一步跳两个台阶不就是dp[i]了么。
使用最小花费爬楼梯
题目
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1
输入 cost [10,15,20]
输出 15
解释 你将从下标为 1 的台阶开始。
支付 15 向上爬两个台阶到达楼梯顶部。
总花费为 15 。
示例 2
输入 cost [1,100,1,1,1,100,1,1,100,1]
输出 6
解释 你将从下标为 0 的台阶开始。
支付 1 向上爬两个台阶到达下标为 2 的台阶。支付 1 向上爬两个台阶到达下标为 4 的台阶。支付 1 向上爬两个台阶到达下标为 6 的台阶。支付 1 向上爬一个台阶到达下标为 7 的台阶。支付 1 向上爬两个台阶到达下标为 9 的台阶。支付 1 向上爬一个台阶到达楼梯顶部。
总花费为 6 。
提示
2 cost.length 10000 cost[i] 999
代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size() 1);dp[0] 0; // 默认第一步都是不花费体力的dp[1] 0;for (int i 2; i cost.size(); i) {dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[cost.size()];}
};题解
确定dp数组以及下标的含义
使用动态规划就要有一个数组来记录状态本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。
对于dp数组的定义大家一定要清晰
确定递推公式
可以有两个途径得到dp[i]一个是dp[i-1] 一个是dp[i-2]。
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] cost[i - 2]。
那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢
一定是选最小的所以dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);
dp数组如何初始化
看一下递归公式dp[i]由dp[i - 1]dp[i - 2]推出既然初始化所有的dp[i]是不可能的那么只初始化dp[0]和dp[1]就够了其他的最终都是dp[0] dp[1]推出。
确定遍历顺序
最后一步递归公式有了初始化有了如何遍历呢
本题的遍历顺序其实比较简单简单到很多同学都忽略了思考这一步直接就把代码写出来了。
因为是模拟台阶而且dp[i]由dp[i-1]dp[i-2]推出所以是从前到后遍历cost数组就可以了。
不同路径
题目
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
示例 1
输入 m 3, n 7 输出 28
示例 2
输入 m 3, n 2
输出 3
解释
从左上角开始总共有 3 条路径可以到达右下角。
向右 - 向下 - 向下向下 - 向下 - 向右向下 - 向右 - 向下
示例 3
输入 m 7, n 3 输出 28
示例 4
输入 m 3, n 3 输出 6
提示
1 m, n 100题目数据保证答案小于等于 2 * 109
题解
dfs
注意题目中说机器人每次只能向下或者向右移动一步那么其实
机器人走过的路径可以抽象为一棵二叉树而叶子节点就是终点
此时问题就可以转化为求二叉树叶子节点的个数 class Solution {
private:int dfs(int i, int j, int m, int n) {if (i m || j n) return 0; // 越界了if (i m j n) return 1; // 找到一种方法相当于找到了叶子节点return dfs(i 1, j, m, n) dfs(i, j 1, m, n);}
public:int uniquePaths(int m, int n) {return dfs(1, 1, m, n);}
};dp dp数组的定义 dp[i][j]表示从(0,0)出发到i,j的不同路径 确定递推顺序 每个位置只有两个方向能走到dp[i][j] dp[i - 1][j] dp[i][j - 1]; 数组初始化 从0,0到i,0的位置一定只有一种到0j也同理 for (int i 0; i m; i) dp[i][0] 1; for (int j 0; j n; j) dp[0][j] 1; 确定遍历顺序 从上方和左边推导过来只要从左往右一层一层遍历即可。
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint(n, 0));for (int i 0; i m; i) dp[i][0] 1;for (int j 0; j n; j) dp[0][j] 1;for (int i 1; i m; i) {for (int j 1; j n; j) {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m - 1][n - 1];}
};凑硬币
题目 题解
dfs
#includebits/stdc.h
using namespace std;
/*
coins硬币的面额列表
amount需要凑的金额
count当前使用硬币的数量
index当前搜索的硬币面额的下标
res存储最少的硬币数量。
*/
void dfs(vectorint coins, int amount, int count, int index, int res) {if (amount 0) {res min(res, count);return;}if (index coins.size()) {return;}for (int k amount / coins[index]; k 0 count k res; k--) {dfs(coins, amount - k * coins[index], count k, index 1, res);}
}int coinChange(vectorint coins, int amount) {sort(coins.rbegin(), coins.rend());int res INT_MAX;dfs(coins, amount, 0, 0, res);return (res INT_MAX ? -1 : res);
}int main() {vectorint coins {1, 2, 5};int amount;cinamount;int res coinChange(coins, amount);cout res endl;return 0;
}dp
#includebits/stdc.h
using namespace std;
int amount;
vectorint coins{1,2,5};int main()
{cinamount;vectorint dp(amount1,amount1);//初始值也为amount 1,是取不到的dp[0]0;for(int i0;idp.size();i){for(auto e:coins){if(i-e0) continue;dp[i]min(dp[i],dp[i-e]1);}}if(dp[amount]amount1) cout-1endl;else coutdp[amount];
}dp数组定义凑其前i金额需要的硬币数量。
初始值也为amount 1,是取不到的
base case自底向上思考dp[0]为0金额为0时就不再需要硬币了
选择从硬币面值组合里面选
状态假设前i-1个已经选完了最后选一个正好凑完
状态转移 dp[i]min(dp[i],dp[i-e]1);需要判断i-e是否0
滑雪
题目 代码
#includebits/stdc.h
using namespace std;
const int N310;
int n,m;
int g[N][N];//不能存在有环图
int f[N][N];//所有从i,j开始滑的路径属性是max
//集合分为四类向上向右向左向下
int dx[4]{-1,0,1,0},dy[4]{0,1,0,-1};int dp(int x,int y)
{int vf[x][y];//引用即为取别名if(v!-1) return v;//表示已经算过了v1;//最小值为1for(int i0;i4;i){int axdx[i],bydy[i];if(a1anb1bmg[x][y]g[a][b])vmax(v,dp(a,b)1);}return v;
}
int main()
{cinnm;for(int i1;in;i)for(int j1;jm;j)cing[i][j];memset(f,-1,sizeof f);//初始化表示每个路径都没被算过int res0;for(int i1;in;i)for(int j1;jm;j)resmax(res,dp(i,j));coutresendl;return 0;
}题解
本题考察使用记忆化搜索优化dp的算法
思路是枚举路径上的每一个点找到最大值而每一个点又能分为四种小的递推的状态因此可以使用动态规划来解决。
dp数组使用一个二维数组来表示路径的长度
属性最大值满足条件即更新
记忆化搜索技巧初始化数组表示没有被算过如果已经被计算过就可以直接返回
汉罗塔
题目 题解
dfs
可以用dfs来搜索所有的情况取最大值
参数
index表示到第几层y表示枚举该层的第一个还是第二个数sum表示总和
#includebits/stdc.h
using namespace std;const int N10;
int f[N][N];int ans;
int n;
void dfs(int index,int y,int sum)
{if(indexn){ansmax(ans,sum);return ;}dfs(index1,y,sumf[index1][y]);dfs(index1,y1,sumf[index1][y1]);
}int main()
{cinn;for(int i0;in;i)for(int j0;ji;j){cinf[i][j];}dfs(0,0,f[0][0]);coutansendl;
}dp
#includebits/stdc.h
using namespace std;const int N10;
int f[N][N];
int dp[N][N];//表示从i,j到最后一层路径中的最大数字之和
int n;int main()
{cinn;for(int i0;in;i)for(int j0;ji;j){cinf[i][j];}for(int i0;in;i){dp[n-1][i]f[n-1][i];//处理边界}//从后往前枚举for(int in-2;i0;i--){for(int j0;ji;j){dp[i][j]max(dp[i1][j],dp[i1][j1])f[i][j];//递推式}}coutdp[0][0]endl;}注意本题是从后往前枚举根据dp数组的定义从i,j到最后一层路径中的最大数字之和也就是要输出
dp[0][0]
01背包问题
题目 代码
#includebits/stdc.h
using namespace std;const int N10010;
int n,V;
int v[N],w[N];
int f[N][N];//从i个物品中选体积不超过jint main()
{cinnV;for(int i1;in;i)cinv[i]w[i];for(int i1;in;i)for(int j1;jV;j){// 当前背包容量装不进第i个物品则价值等于前i-1个物品if(jv[i]) f[i][j]f[i-1][j];// 能装需进行决策是否选择第i个物品else{f[i][j]max(f[i-1][j],f[i-1][j-v[i]]w[i]);}}coutf[n][V]endl;}题解 摘花生
题目 代码
#includebits/stdc.h
using namespace std;const int N110;
int a[N][N];
int dp[N][N];//从(1,1)到(i,j)所有路径中能摘得花生最多的路径
int t;
int n,m;
int main()
{cint;while(t--){cinnm;for(int i1;in;i)for(int j1;jm;j)cina[i][j];for(int i1;in;i)for(int j1;jm;j)dp[i][j]max(dp[i-1][j]a[i][j],dp[i][j-1]a[i][j]);coutdp[n][m]endl;}}题解
用闫式dp法来分析 最长上升子序列
题目 代码
#includebits/stdc.h
using namespace std;
const int N1010;int a[N];
int dp[N];//表示以i结尾的最长上升子序列
int n;
int main()
{cinn;for(int i1;in;i)cina[i];for(int i1;in;i)dp[i]1;for(int i1;in;i)for(int j1;ji;j){if(a[i]a[j])dp[i]max(dp[i],dp[j]1);}int res0;for(int i1;in;i)resmax(res,dp[i]);coutresendl;
}题解 总结
动态规划是一种非常重要的算法思想它可以解决很多实际问题并且在计算机科学领域中有着广泛的应用。通过本博客的学习我们可以了解到动态规划的基本概念、算法原理和应用场景。
在实际应用中动态规划算法可以用于解决很多优化问题如背包问题、最长公共子序列问题、最短路径问题等。学习动态规划算法不仅可以提高算法设计和解决问题的能力还可以帮助我们更好地理解计算机科学中的一些基本概念和方法。
总之动态规划算法是一种非常重要的算法思想需要我们不断地学习和实践才能更好地掌握它的精髓并将其应用到实际问题中。希望本博客能够为读者提供一些启示和帮助促进大家在算法学习和实践中的进步和成长。也祝大家考出好成绩
