网站用视频做背景音乐,做招聘网站创业,wordpress添加顶部导航条,湟中网站建设第33天#xff0c;动态规划开始#xff0c;新的算法#x1f4aa;(ง •_•)ง#xff0c;编程语言#xff1a;C
目录
动态规划理论基础
动态规划的解题步骤
动态规划包含的问题
动态规划如何debug
509.斐波那契函数
70.爬楼梯
746.使用最小花费爬楼梯
总结 动态…第33天动态规划开始新的算法(ง •_•)ง编程语言C
目录
动态规划理论基础
动态规划的解题步骤
动态规划包含的问题
动态规划如何debug
509.斐波那契函数
70.爬楼梯
746.使用最小花费爬楼梯
总结 动态规划理论基础 文档讲解代码随想录动态规划理论基础 动态规划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数组中下标表示的含义这样才能够有助于我们真正理解题目。
对于动态规划问题我们可以把解题步骤拆解为如下五步
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组打印dp数组
解题过程中依据上述5步进行。注意对dp数组的初始化是在确定递推公式后的因为有些初始化是要依据递推公式进行的。
动态规划包含的问题
动态规划一般包含的问题有
基础题目背包问题打家劫舍股票问题子序列问题
动态规划是一个很大的领域对于后面的每一种问题还需要进行单独的讲解。
动态规划如何debug
我们在解动态规划问题时如果出现无法通过的时候一定不要慌张代码出现问题是很正常的。我们最重要的是不能让代码对我们而言是黑盒状态就是我们都不确定它的运行顺序和结果。
最好的debug方式就是把dp数组打印出来看看结果究竟是不是按照自己思路推导的又是哪一个部分出了错误。
同时做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。
在对动态规划问题进行debug时我们一定要牢记三个问题
这道题目我举例推导状态转移公式了么我打印dp数组的日志了么打印出来了dp数组和我想的一样么
牢记上述三个问题基本就能够解决动态规划解题过程中遇到的问题。 509.斐波那契函数 文档讲解代码随想录斐波那契函数 视频讲解手撕斐波那契函数 题目 学习本题是非常经典的数学题目之一也是标准的动态规划题目。递推公式在题干中就已经给了我们剩下的就是我们依照动规五部曲逐步进行。
1.确定dp数组以及下标的含义在这里我们可以定义一个vector型的dp数组dp[i]定义为第i个斐波那契数值。
2.确定递推公式dp[i] dp[i - 1] dp[i - 2]
3.dp数组初始化根据递推公式我们知道至少要有两个数才能够递推下去。因此我们需要初始化dp[0] 0; dp[1] 1
4.确定遍历顺序从递归公式中我们发现dp[i]是依赖于dp[i - 1]和dp[i - 2]的因此遍历顺序一定要从前往后进行遍历。
5.举例推导dp数组我可以依照我们上述构造的dp数组和递推关系当n 10时dp数组应该为011235813213455。如果发现结果不对我们也可以通过打印dp数组来查看问题出在哪。
代码
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int fib(int n) {//动态规划使用dp数组存储斐波那契数列数值if(n 2) return n; //0,1单独处理vectorint dp(n 1); //从0-Ndp(n)表示第n个数的斐波那契数值dp[0] 0;dp[1] 1;for(int i 2; i n; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};
代码对于本题来说实际上也可以不适用dp数组我们只需要维护两个值就可以了
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:int fib(int n) {//动态规划不使用dp数值只找到第n个值if(n 2) return n;int dp0 0;int dp1 1;int sum;for(int i 2; i n; i) {sum dp0 dp1;dp0 dp1;dp1 sum;}return dp1;}
};
代码本题还可以使用递推公式进行代码极度简便但并不好想。
//时间复杂度O(2^n)
//空间复杂度O(n)
class Solution {
public:int fib(int n) {//递归法非常恐怖if(n 2) return n;else return fib(n - 1) fib(n - 2);}
}; 70.爬楼梯 文档讲解代码随想录爬楼梯 视频讲解手撕爬楼梯 题目 学习本题实际上是斐波那契数的变种递推公式都是一样的。这也可见动态规划问题能够想出递推公式确认是十分重要的。
对于本题来说由于一次可以爬1或2个台阶因此对于第3层台阶来说可以从第一层爬2层台阶到达也可以从第二层爬1层台阶到达。而到达第一层和第二层的种类分别是dp[1]和dp[2]因此到达第三层的种类就为dp[1]dp[2]之后的第四层也是如此能够通过从第二层爬2阶到达也能够通过从第三层爬1阶到达……
最后就能够得到同样的递推公式dp[n] dp[n - 1] dp[n - 2]。但要注意本题中与斐波那契数不同的式dp[0]在本题中是没有意义的虽然我们给dp[0]赋值为1(因为dp[2]2也能够解决问题但是dp[0]是没有实际意义的因此本题更推荐给dp[1]和dp[2]进行初始化。
代码
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int climbStairs(int n) {//动态规划//1.确定dp数组以及下标的含义vectorint dp(n 1); //dp(n)表示爬n阶的方法//2.确定递归条件dp(n) dp(n - 1) dp(n - 2);//3.dp数组初始化因为dp(0)是没有意义的且n也不会等于0因此不需要初始化0if(n 1) return n;dp[1] 1;dp[2] 2;//4.确定遍历顺序for (int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];//5.举例推导dp数组打印dp数组//cout dp[i] endl;}return dp[n];}
}; 746.使用最小花费爬楼梯 文档讲解代码随想录使用最小花费爬楼梯 视频讲解手撕使用最小花费爬楼梯 题目 学习本题我们需要注意题干中的两个点1.cost[i]是从i个台阶向上爬需要支付的费用也就是我们只有向上爬了才需要支付费用我们站在i台阶上是不需要支付cost[i]的。2.到达楼梯顶部不是指第最后的下标(cost.size() - 1)个台阶实际上根据例子我们可以发现是最后一个台阶还要再上一个台阶才是顶部的位置。
基于此我们可以通过递归五部曲来求解本题。
1.确定dp数组以及下标的含义我们可以构造一个vector型dp数组其中dp[i]应该定义为到达第i个台阶所花费的最小体力这样我们最后求出的dp[cost.size()]才是到达顶部的花费最小体力。
2.确定递推公式对于第i个台阶来说有两个途径能够得到dp[i]一个是dp[i - 1]一个是dp[i - 2]而我们需要得到最小的因此dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])。
3.初始化dp数组通过递推公式我们知道至少需要两个数才能够推出后面的值因此我们可以初始化dp[0] 和 dp[1]注意本题中题干给出了0下标的含义
4.确定遍历顺序显然本题也是从前往后进行遍历。
5.举例推导dp数组 代码
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int minCostClimbingStairs(vectorint cost) {//动态规划//1.确定dp数组及下标含义vectorint dp(cost.size() 1); //dp[n]表示上到第n个台阶所要消耗的最小花费//2.确定递推公式 dp[n] min(dp[n - 1] cost[n - 1], dp[n - 2] cost[n - 2]);//3.dp数组初始化(规定cost.size() 2)dp[0] 0; //爬的时候才消耗费用dp[1] 0;//4.确定遍历顺序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()];}
};
总结
动态规划开始牢记动态五部曲做题不慌张。
