基本算法练习——接金币

基本算法练习——接金币

问题描述：

实质上是求最优组合的问题。

代码如下：

#include #include using namespace std;int receive(vector>& matrix,int time,int pos,int maxT){ //出栈条件 int res=0; if(pos<0||pos>10) return 0; if(time==maxT) return matrix[time][pos]; //进栈条件 int res1 = receive(matrix,time+1,pos-1,maxT); int res2 = receive(matrix,time+1,pos+0,maxT); int res3 = receive(matrix,time+1,pos+1,maxT); //栈中处理 int maxRes=0; maxRes = max(res1,res2); res = max(maxRes,res3)+matrix[time][pos]; return res;}int main(){ int n; cin>>n; vector> xtPair; int maxT=0; for(int i=0;i>x>>t; xtPair.push_back(pair(x,t)); if(maxT> matrix(maxT+1,vector(11,0)); vector>::iterator it; for(it=xtPair.begin();it!=xtPair.end();it++){ int t = it->second; int x = it->first; matrix[t][x]++; } cout<

笔记：

1.对于多种多样的组合，如何进行遍历描述呢？   答： 使用 递归。

2.使用递归可以描述组合问题，使用层次最优可以使总体组合达到最优。

3.不同的维度可以通过增加数组的维度进行描述。如时空可以通过矩阵描述。

对本问题的图形描述:

比较难理解的是层次最优向上传递的问题。

这个递归函数包含两个return,

第一个return是负责出栈的，用于完成组合；

第二个return是负责层次最优向上传递的，用于完成最优；（其中，最难理解的是这个res变量，它是向上层传递的关键。）

此外，要注意，maxT 与t 在数制上的不同，因此问题矩阵的维度必须增加1.

为了方便，可以将第二个return称为 递归反馈。通常情况下，它代表了递归函数返回值的意义。

针对本问题，有一个更简单的方法，那就是将每条路径都存储起来，然后路径求和，排序即可的最优与最差路径。那样就可以不设置递归反馈，即递归函数的返回值为 void 。 问题规模将简单很多。  但是效率有所下降。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。