首页 > 代码库 > 递归讨论（二）续
递归讨论（二）续
在讨论二中，展示了钢条分段的方法，只不过解题的方法采用的是自顶而下的策略。
个人理解的自顶而下的策略：
首先我们不知道一个大问题的答案，但我们可以将问题规模缩小，外加上已知的一部分。进而变成求解这个小规模问题答案的过程，利用递归原理，层层向下，最终回到一个最简单的问题。
这种处理问题的方式，难免会有重复求解的情况出现。上篇中也有提到！！！
先还是把上篇的部分代码搞过来看看。
int get_max(int* price,int* len,int num,int *p)//新增的这个指针p指向一个记录数组，下标为长度num-1，我们用来记录对应长度num下的最大收益{ int result=0; if(num>=1&&p[num-1]>=0) //此处判断就起到从记录表中查值作用。 return p[num-1]; if(num == 0)//由标记A处的num-len[i]以及其上的if判断,可以看出下次调用get_max时,可能出现num为0的情况 return 0; for(int i=1;i<=6;i++) { if(num >=len[ i-1]) { result = std::max(result,get_max(price,len,num-len[i-1],p)+price[i-1]);//标记A处 } } p[num-1] = result; return result;}
从代码中，我们可以粗略计算下，总共调用了多少次get_max()；首先在不断的调用中，get_max()函数中的num值取遍了0-num，权且计作num次
在每次调用中，我们都需要for()循环下，（因为粗略计算嘛）我们就不考虑其中的if判断了。
最终我们计算出的调用次数：num*6，很类似双层循环啊
看num值从0变化到num的最大值
价格从1到6变化，嵌套在num的每次变化，显然是双层循环了。
我们再分析下：
上述程序中，每次调用的get(..num..)，都为了计算当前num的最大收益的吧。只不过大的num根据小的num计算出来，通过递归调用实现，但按照程序的实际运行的顺序来说，最终还是小num的最大收益先被计算出，然后返回给大的num的使用。这是一种从顶向下，然后结果再层层上返回的过程。
与其这么麻烦，我们不如先计算小num，然后将小num的值贡献给比它大的num，这样就减少了递归那样不断的调用了。（自下而上的策略）
这样做的要求就是：我们必须保证num从1到最大时，每个循环都获得当前num下的最大的收益，先上代码好了：
void get_max(int* len,int* price,int n,int num,int *p,int* s)//其中n表示可分段种类数 num为钢条长度，p记录的当前num下首次截断的长度，下标为num，s记录的当前num下最大收益{ s[0] = 0; for(int i=1;i<=num;i++) { int q = 0;//当前num下，q用于第二层循环的最大收益的记录 for(int j=0;j<n;j++) { if(i>=len[j]) { s[i] = s[i-len[j]]+price[j]; } if(s[i] > q)//当条件成立时，说明当前num下，最大收益的组合被更新了哦 { q = s[i];
p[i]=j; } } s[i] = q; }}
这样我们就获得最大收益，同时也可以获得如何分段的方法。
同时一定程度也减少了程序的复杂性。
如果下次再碰到动态规划问题，就想想这个！理解比较浅薄，望指教！
递归讨论（二）续
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。