新手就是爱记录--动态规划(c++) 1

刚入门编程师在刚接触算法时常常会听到“动态规划找最优解”但每次面对题目总是摸不着头脑。动态规划本质就是将大问题拆分成小问题并将结果保存起来最终得到答案。这样可以避免重复计算使得运行超时。我们先从简单的一道基础题目开始1.跳台阶 一共有n级的台阶每次只能跳一格或者两格请问从0到n级有多少种方案在高中数列的学习中这是一道简单的递归题目每一次的跳跃均有两种可能每一次的结果都存在两种可能我们每一次的结果都存在两种可能性那么得出方程f(i)f(i-1)f(i-2)这个相信每个人都能推出来那么我们需要考虑的就是用代码展示出来而作为一个新手小白最希望的解决方法是什么就是暴力枚举但这个暴力枚举不同的就是需要记忆化搜索存储跳跃结果这里我提供参考代码#includebits/stdc.h using namespace std; typedef long long ll; const int N20; ll jy[N]; ll dfs(ll x){ if(jy[N]N) return jy[N]; ll sum0; if(x1){ sum1; } else if(x2){ sum2; } else{ sumdfs(n-1)dfs(n-2);//存在两种可能要么一次跳一阶一次跳两阶 } jy[x]sum; return sum;//得出最后结果 } int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n; cinN; ll ansdfs(n); coutansendl; return 0; }这里使用了一个记忆化数组jy如果达到了n的台阶就结束如果没有则将继续回溯寻找结果。分析该跳台过程以6为例子从3向下寻找的过程称作递从小向上回溯称为归所以递归问题从本质上来讲就是自上而下分解再从下往上寻求结果。这里再提供简单的递归代码:#includebits/stdc.h using namespace std; typedef long long ll; const int N20; int main(){ ios::sync_with_stdio(fasle); cin.tie(0); ll n; cinn; ll f[N]; f[1]1,f[2]2; for(int i1;in;i){ f[i]f[i-1]f[i-2]; } coutf[n]endl; return 0; }ps洛谷上面的题目提交我的这部分代码无法ac因为提供的数据过大会超时需要高精度解决不了解的可以去翻找我上篇文章自己尝试欢迎在评论区讨论。通过了上一题目的分析我们对于递归的本质有了一点儿理解下面我们进入下一部分依旧再来一题。2.打家劫舍现在你是一个专业小偷打算偷沿街的一排房子。每一间房子都有一定数量的现金但相邻的房子不可以同时被偷否则会触发警报你需要计算出可以偷盗的最大金额。我们先从小白的视角来看从只有一间房到两间房选择更大的三间房先比较隔间房子之和与最大。从理论上来讲我们可以列举出所有情况选出最大值即可但这会导致数据过大运行超时那么我们优化思路。对于第四间房我们需要考虑偷还是不偷。偷第三间不能偷不偷就保留前三间房子的最大优化解。这样子来看是不是发现问题变得简单了我们再将所想的用方程式去表达假设我们再第n间房子偷则f(n)f(n-2),不偷则是f(n-1)最终结果动态转移方程f(i)max((f(i-1),f(i-2)num[i])这样分析对于每一次均为两种选项将复杂的问题简单化但这个时候我们可以发现我们有三种思路去解决这个问题1.自底向上 2. 自顶向上 3. 记忆化。虽说是三种考虑方式但源头都是在钰上述的动态转移方程。下面提供三种解答代码1.第一种#includebits/stdc.h using namespace std; typedef long long ll; const int N200; ll num[N]; ll jy(ll x){ if(x0) return 0; if(x1) return num[0]; ll q1num[0]; ll q2max(num[0],num[1]); for(int i2;in;i){ ll cxymax(q1,q2num[i])//cxy仅仅作为中间变量名并无实际存在意义 q2q1,cxyq1;//重新赋值 } return q1; } int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n; cinn; for(int i0;in;i){ cinnum[i]; } coutjy(n)endl; return 0; }2.第二种#includebits/stdc.h using namespace std; typedef long long ll; const int N200; ll num[N]; ll jy(int x){ if(x0) return 0;//打完才发现其实无需特判懒得改了 return max(jy(x-1),jy(x-2)num[x]); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cinn; fro(int i0;in;i){ cinnum[i]; } coutjy(n)endl; return 0; }3.第三种#includebits/stdc.h using namespace std; typedef long long ll; const int N200; ll num[N]; ll me[N]; int dp(int x){ if(me[x]!-1) return me[x]; ll summax(dp(x-1),dp(x-2)num[x]); me[x]sum; return sum; } int jy(int n){ memset(me,-1,sizeof(me)); return dp(n-1); } int main(){ ios::sync_with_stdio(false); cin.tie(0); ll n; cinn; for(int i0;in;i){ cinnum[i]; } coutjy(n)endl; return 0; }后面这几个有点潦草确实今天有点累了有疑问的可以向我提出来欢迎大家的批评指正。学到这里对于动态规划虽说没有得心应手但至少有了印象下期我们将继续深入学习分析动态规划算法帮助大家理解哦。明天有cf可能要后天更新了吧。kskblzdjd.嘻嘻依旧夹带私货edg20wol懂你意思。我是超级无敌大笨蛋菜鸟欢迎大家在评论区讨论不喜勿喷不喜勿喷球球大家点点赞让我有继续更新的动力我也希望我能将这个新手就是爱记录这个系列做下去马上新的大一就要入学了计算机将涌入新的血液有新的新手希望这系列能够帮助每一个新手我们下期文章再见喽。