网站倒计时怎么做,成都网站制作创新互联,北京智能网站建设制作,做电影网站如何盈利动态规划如何学习
参考灵神的视频和题解做的笔记#xff08;灵神YYDS#xff0c;以后也都会用这套逻辑去思考#xff09;
枚举选哪个#xff1a;
动态规划入门#xff1a;从记忆化搜索到递推_哔哩哔哩_bilibili
746. 使用最小花费爬楼梯 - 力扣#xff08;LeetCode灵神YYDS以后也都会用这套逻辑去思考
枚举选哪个
动态规划入门从记忆化搜索到递推_哔哩哔哩_bilibili
746. 使用最小花费爬楼梯 - 力扣LeetCode 选或不选
0-1背包 完全背包_哔哩哔哩_bilibili 494. 目标和 - 力扣LeetCode
个人觉得枚举选哪个和选或不选的区别是 枚举选哪个是在回溯函数中有for循环 而选或不选只有两个选择一般会是二叉树 文章目录 动态规划如何学习学习步骤枚举选哪个746.使用最小花费爬楼梯第一步回溯法深度优先遍历第二步改成记忆化搜索第三步一比一翻译成动态规划(递推)优化 选或不选01背包模板可以配合该视频和代码随想录博客一起看第一步回溯法深度优先遍历第二步改成记忆化搜索第三步一比一翻译成动态规划(递推)滚动数组代码 学习步骤
1.思考递归回溯的暴力穷举法即深度优先遍历DFS
注意要画树形结构画完很容易看出哪里是重复的计算对改成记忆化搜索有好处
可以使用代码随想录的递归三部曲
2.改成记忆化搜索就是准备一个备忘录数组保存已经计算过的结果
3.把记忆化搜索1:1翻译成为DP
翻译的时候可以想想代码随想录的动规五部曲其实到这里五部曲的内容已经全部解决了
刷了几道题以后的发现 1.思考回溯的时候一般就会把dp数组和下标的含义给想清楚这一过程就是分割子问题的过程不然回溯想不出来的
2.回溯算法终止条件一般是dp数组的初始化
3.记忆化搜索一般是自底向上和动态规划的从前往后其实是一样的只是记忆化是递归里的栈而动态规划是for循环
4.dfs函数就是dp数组
5.dfs一般传入的参数n在动态规划里面一般是一层for循环dfs中如果有for循环那动态规划的递推一般是两层循环而且n可以和循环中的一个进行替换 **动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。**在做题时可根据题目要求选择适合题目的一种来思考。
枚举选哪个
746.使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣LeetCode
第一步回溯法深度优先遍历
这个过不了时间复杂度太高但是这是学习动态规划的必由之路
思路
首先思考子问题并画出树形结构图
我们要求到第5个台阶的最小花费我们可以从第4个加上4的花销上一个台阶也可以从3加上3的花销上两个台阶
我们要求到第n个台阶的最小花费我们可以从第n-1个加上n-1的花销上一个台阶也可以从n-2加上n-2的花销上两个台阶n-1就是下一个要求的子问题由n-2和n-3得到一直到1或2它的花费就是0因为可以选择从1或2开始爬楼梯
这样就得到了一个二叉树以5为例子
我们要到5的台阶就要依靠到达4和到达3的结果来比较得到最小值所以要得到下层结点向上层返回的结果那就得用后序遍历来得到4,3的结果 1.返回值和参数
我们要下层结点的最小值所以要int
cost是题目中的花费数组index是记录我们遍历到哪里了相当于for循环里面的i
int dfs(vectorint cost,int index)2.终止条件
if(index0||index1)return 0;0其实是第一个台阶1其实是第二个台阶因为cost数组从0开始。
爬第一个或第二个台阶不需要花费所以直接返回0
3.本层逻辑
左子树返回爬上第n-1台阶的最小值
右子树返回爬上第n-2台阶的最小值
最后本层返回的就是两者的最小值作为结果
int ldfs(cost,index-1)cost[index-1];
int rdfs(cost,index-2)cost[index-2];
return min(l,r);完整代码
class Solution {
public:int dfs(vectorint cost,int index){if(index0||index1)return 0;int ldfs(cost,index-1)cost[index-1];int rdfs(cost,index-2)cost[index-2];return min(l,r);}int minCostClimbingStairs(vectorint cost) {return dfs(cost,cost.size());}
};C还可用lambda来写
class Solution {
public:int minCostClimbingStairs(vectorint cost) {functionint(int) dfs[](int index)-int{if(index0||index1)return 0;return min(dfs(index-1)cost[index-1],dfs(index-2)cost[index-2]);};return dfs(cost.size());}
};第二步改成记忆化搜索 从图中可以看到这些地方就是重复计算的地方可以直接砍掉。
怎么砍呢
我们在遍历过程中如果是第一次碰到这个数字呢我们就把它的计算结果给保存到一个数组当中去下次要用的话直接从数组里面拿而不用再次进行递归计算了。
砍完之后还剩下啥只需要计算3,4,5你会发现时间复杂度竟然变成了O(n)成了线性的那这不就和递推一样了么用1,2计算3用2,3计算4用3,4计算5得出结果。
在递归进行记忆化搜索里面这是自底向上的计算算5要去递归3,4然后一层一层递归
到最后1和2的时候直接返回0然后得出3的最小然后根据2,3得出4的最小最后一层一层返回知道最后。
下面就来看递推。
完整代码
class Solution {
public:int dfs(vectorint cost,vectorint dp,int index){if(index0||index1)return 0;//碰到了算过的那就直接返回if(dp[index]!-1)return dp[index];int ldfs(cost,dp,index-1)cost[index-1];int rdfs(cost,dp,index-2)cost[index-2];return dp[index]min(l,r);//1.return dp[index]min(dfs(cost,dp,index-1)cost[index-1],dfs(cost,dp,index-2)cost[index-2]);这样写也行//2.dp[index]min(l,r);//return dp[index];也行}int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()1,-1);return dfs(cost,dp,cost.size());}
};class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()1,-1);functionint(int) dfs[](int index)-int{if(index0||index1)return 0;if(dp[index]!-1)return dp[index];int resdp[index];return resmin(dfs(index-1)cost[index-1],dfs(index-2)cost[index-2]);};return dfs(cost.size());}
};注意点 1.传入的dp备忘录必须是引用传入不然的话下层的结果保存不到数组里面每一层的dp数组还全都是-1就和DFS逻辑一样了其实。dp数组不会起到任何作用
2.对dp[index]一定要赋值不能直接返回min(l,r)不然dp数组不会更新
3.l和r不可以替换成dp[index-1]和dp[index-2]。如果有小伙伴不幸和一样犯了这个错误那就继续看吧
int dp[index-1]dfs(cost,dp,index-1)cost[index-1];
int dp[index-2]dfs(cost,dp,index-2)cost[index-2];
return dp[index]min(l,r);我先说答案这种乍一看挺对的实际上没有想清楚dfs返回值到底是什么dfsindex-1的返回值是dp[index-1]如果再加上cost[index-1]那得到的应该是dp[index]而不是dp[index]。
下面是我没彻底弄懂之前写的只是记录一下自己的思考过程不想看的可以跳过了
这种方式会刷新我们已经保存过的dp[index]就比如起始的0和1dp[0]和dp[1]花费最小值本来都是0但是用这个在计算dp[3]的时候会把dp[0]和dp[1]赋值为cost[0]和cost[1]。
然后dp[2]dp[0]cost[0]2可是我们一看这肯定是1怎么能是2呢
后面的dp[3]也是最开始被更新为3后面直接变成4了这就是再次刷新了
输入
cost
[1,100,1,1,1,100,1,1,100,1]
标准输出
index2
1 100 -1 -1 -1 -1 -1 -1 -1 -1 -1
index3
1 100 2 -1 -1 -1 -1 -1 -1 -1 -1
index4
1 100 3 3 -1 -1 -1 -1 -1 -1 -1
index5
1 100 3 4 4 -1 -1 -1 -1 -1 -1
index6
1 100 3 4 5 104 -1 -1 -1 -1 -1
index7
1 100 3 4 5 204 6 -1 -1 -1 -1
index8
1 100 3 4 5 204 7 7 -1 -1 -1
index9
1 100 3 4 5 204 7 8 107 -1 -1
index10
1 100 3 4 5 204 7 8 207 9 -1 正确的打印
cost
[1,100,1,1,1,100,1,1,100,1]
标准输出
index2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
index3
-1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1
index4
-1 -1 1 2 -1 -1 -1 -1 -1 -1 -1
index5
-1 -1 1 2 2 -1 -1 -1 -1 -1 -1
index6
-1 -1 1 2 2 3 -1 -1 -1 -1 -1
index7
-1 -1 1 2 2 3 3 -1 -1 -1 -1
index8
-1 -1 1 2 2 3 3 4 -1 -1 -1
index9
-1 -1 1 2 2 3 3 4 4 -1 -1
index10
-1 -1 1 2 2 3 3 4 4 5 -1 第三步一比一翻译成动态规划(递推)
1.确定dp数组以及下标的含义
dp数组含义是登上第i个台阶由多少种方法
i下标就是第i1个台阶
2.确定递推公式
dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);这个就是在回溯的两个选择里面挑一个小的
就是记忆化搜索里面的返回值
3.dp数组如何初始化
就是回溯里面的终止条件
vectorint dp(cost.size()1,-1);
dp[0]0,dp[1]0;4.确定遍历顺序
后面的5要依靠前面3,4的计算结果所以肯定是正向遍历
完整代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()1,-1);dp[0]0,dp[1]0;for(int i2;icost.size();i)dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);return dp[cost.size()];}
};优化
其实也不需要把所有的结果全都给记住只需要记住i的前一个i-1b和前前一个i-2a
class Solution {
public:int minCostClimbingStairs(vectorint cost) {//adp[0],bdp[1]int a0,b0;for(int i2;icost.size();i){int cmin(acost[i-2],bcost[i-1]);ab;bc;} //cdp[i] adp[i-1] bdp[i]然后下一次循环的时候ia就变成dp[i-2],b变成dp[i-1]return b;}
};选或不选
0-1背包 完全背包_哔哩哔哩_bilibili
01背包模板可以配合该视频和代码随想录博客一起看 恰好装这个容量求方案数量的最大最小价值和那就是把选最大值的操作换成加号
494. 目标和 - 力扣LeetCode
后续如果做到了其他的变形题目会同步更新到这里
第一步回溯法深度优先遍历
思路
配合视频一起看更棒
0-1背包 完全背包_哔哩哔哩_bilibili 下面的就不画了大家知道这个意思就行
选编号为i的话就是返回dfs(i-1,c-w[i])v[i]就是代表已经把编号为i的物品已经放入了背包表现为容量减了w[i]价值加了v[i]然后继续递归下一个物品
不选编号为i的话就是返回dfs(i-1,c)这个代表的是一共有i-1个物品总共是c的容量那背包能装的最大价值是多少
我们本层函数会产生两个递归一个是选了i一个是没选i返回的都是对应情况的最大值我们要选最大的所以要在这两个里面再选一个更大的作为返回值返回
从而得出了递推公式。
这个虽然过不了时间复杂度太高但是这是学习动态规划的必由之路
1.返回值和参数
w各个物品所占空间
v各个物品价值
i遍历物品
c是当前剩余的容量
返回值返回选或不选编号为i的物品的最大值
int dfs(vectorint w,vectorint v,int i,int c)2.终止条件
if(i0)return 0;
if(cw[i])return dfs(w,v,i-1,c);如果编号小于0说明已经到了树形结构最下面了要开始从第一个物品选了即自底第一个物品向上i依次增大开始遍历
如果当前容量已经小于要选的物品那就直接返回给上层不选i号物品的结果
3.本层逻辑
在选和不选当前物品两种情况中只要返回回来的一定是最大值挑一个更大的返回
return max(dfs(w,v,i-1,c),dfs(w,v,i-1,c-w[i])v[i]);完整代码
class Solution {
public:int dfs(vectorint w,vectorint v,int i,int c){if(i0)return 0;if(cw[i])return dfs(w,v,i-1,c);return max(dfs(w,v,i-1,c),dfs(w,v,i-1,c-w[i])v[i]);}int 01knapsack(vectorint nums,int c) {vectorint w(nums.begin(),nums.end());vectorint v(nums.begin(),nums.end());return dfs(w,v,nums.size()-1,c);}
};C还可用lambda来写
class Solution {
public:int 01knapsack(vectorint nums,int c) {vectorint w(nums.begin(),nums.end());vectorint v(nums.begin(),nums.end());functionint(int,int) dfs[](int i,int c)-int{if(i0)return 0;if(cw[i])return dfs(i-1,c);return max(dfs(i-1,c),dfs(i-1,c-w[i])v[i]);};return dfs(nums.size()-1,c);}
};第二步改成记忆化搜索
注意在递归函数中我们同时有物品编号i和容量c所以要用一个二维数组作为哈希表来存储计算结果进行复用。
然后在每次返回结果前都赋值一下把计算结果给存储起来
完整代码
class Solution {
public:int dfs(vectorint w,vectorint v,int i,int c,vectorvectorint dp){if(i0)return 0;if(dp[i][c]!-1)return dp[i][c];if(cw[i])return dp[i][c]dfs(w,v,i-1,c,dp);return dp[i][c]max(dfs(w,v,i-1,c,dp),dfs(w,v,i-1,c-w[i],dp)v[i]);}int 01knapsack(vectorint nums,int c) {vectorint w(nums.begin(),nums.end());vectorint v(nums.begin(),nums.end());vectorvectorint dp(nums.size(),vectorint(c1,-1));return dfs(w,v,nums.size()-1,c,dp);}
};class Solution {
public:int 01knapsack(vectorint nums,int c) {vectorint w(nums.begin(),nums.end());vectorint v(nums.begin(),nums.end());vectorvectorint dp(nums.size(),vectorint(c1,-1));functionint(int,int) dfs[](int i,int c)-int{if(i0)return 0;if(dp[i][c]!-1)return dp[i][c];if(cw[i])return dp[i][c]dfs(i-1,c);return dp[i][c]max(dfs(i-1,c),dfs(i-1,c-w[i])v[i]);};return dfs(nums.size()-1,c);}
};第三步一比一翻译成动态规划(递推)
1.确定dp数组以及下标的含义
二维数组dp[i][c]就是第i个物品在容量为c时可以取到的最大价值
i是物品编号
c是当前背包的总容量
2.确定递推公式
对应回溯算法本层逻辑部分
选或者不选第i号物品如果没选那就和上一个物品第i-1件遍历到j时一样的价值因为没有选第i号
如果选了那就是 第i-1件物品在j-w[i]时的价值选择的第i件物品的价值v[i]
dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]);3.dp数组如何初始化
全都初始化为0
第一行在容量大于第一件物品所需容量的时候就当做把第一件给放了进行初始化
因为dp[0][i]的物品编号只有0即第一件物品所以只能选择第一件物品得到最大价值不选的话价值就为0
vectorvectorint dp(nums.size(),vectorint(c1,0));
for(int iw[0];ic;i)dp[0][i]v[0];4.确定遍历顺序 从前往后遍历先遍历物品或者先遍历容量都是可以的因为先物品是按照行一行一行来遍历递推公式中的两个值都可以在遍历得出来按照容量一列一列遍历也同样可以得出来这两个值
但仅限于二维如果是一维那就只能先遍历物品后遍历容量而且只能从后往前遍历容量
因为递推公式中用到的两个值在一维中变成了这样
vectorint dp(c1,0);
for(int i0;inums.size();i)for(int jc;jw[i];j--)dp[j]max(dp[j],dp[j-w[i]]v[i]);第一行是刷新前的数组第二行是要对第一行进行覆盖的值通过第一行的dp[j]和dp[j-w[i]]这两个值进行更新
如果从前往后那dp[j-w[i]]就会被覆盖从而得到一个错误的答案
如果不太理解可以转至代码随想录
0-1背包 完全背包_哔哩哔哩_bilibili视频里面也会讲到滚动数组相关
for(int i1;inums.size();i)
for(int j0;jc;j)if(jw[i])dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]);elsedp[i][j]dp[i-1][j];完整代码
class Solution {
public:int 01knapsack(vectorint nums,int c) {vectorint w(nums.begin(),nums.end());vectorint v(nums.begin(),nums.end());vectorvectorint dp(nums.size(),vectorint(c1,0));for(int iw[0];ic;i)dp[0][i]v[0];for(int i1;inums.size();i)for(int j0;jc;j)if(jw[i])dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]);elsedp[i][j]dp[i-1][j];return dp[w.size()-1][c];}
};滚动数组代码
class Solution {
public:int 01knapsack(vectorint nums,int c) {vectorint w(nums.begin(),nums.end());vectorint v(nums.begin(),nums.end());vectorint dp(c1,0);for(int i0;inums.size();i)for(int jc;jw[i];j--)dp[j]max(dp[j],dp[j-w[i]]v[i]);return dp[c];}
};
