递归一直给人的感觉是简洁且优雅，但是在面对较大规模的问题时，递归的弊端就渐渐暴露出来了。因为大量栈的使用导致程序运行速度变得很慢，所以递归算法需要改进。
1.尾递归：函数返回之前的最后一个操作若是递归调用，则该函数进行了尾递归。
但是我发现尾递归貌似并没有很显著的作用？？？（值得深究）
2.递归改递推，举例斐波拉切数列
递归算法大于40之后就会变得很慢，甚至算不出来。而递推算法可以算更大的数而且算得更快（即使用了long，但是超过50还是会溢出gg）。
所以面额拼凑问题就需要使用递推法，一个一个算，看似非常傻但是却比递归好用，或许这就是大智若愚吧。
可以算10000的递推算法
比较难理解的可能是m[j]+=m[j-den[i]];其等价于之前提到的递推式（1020,100）=（1020-100,100）+（1020,50），但是我们发现（1020,50）没了，这是因为之前已经加上去了。
在这个两层循环中，第一层就是以不同的面额做循环，例如（5,5）=（0,5）+（5,1），之所以省略掉了（5,1）是因为在之前就已经将（5,1）加上去了（m[j]=1）,所以可以直接m[j]+=m[j-den[i]].当面额为5循环完毕之后，就可以开始面额为10的循环了。（10,10）=（5,10）+（10，1）=（5,5）+（10,1），由于之前（10,1）已经加上去了，所以直接加上（5,5）就可以了。一次类推直到面额100循环完毕，结果就出来了。（感觉没有讲清楚）
碰到的问题：
1.10000的时候出现溢出。原因：之前在intellij（java）中写的时候用long（64位）没问题，但是C语言（dev c++和VS）long是32位的，所以使用long long
2.dev c++使用的是gcc编译器支持动态数组，VS不支持所以一开始报错。改为long long *m=new long long[money+1];
网友评论