换硬币 （C语言代码）记忆化搜索

解题思路:递归求斐波那契数列，都知道吧；这里注意说说优化问题（再递归上面），先看看：

                                                            fb(10)

                            fb(9)                                                            fb(8)

                fb(8)                 fb(7)                              fb(7)                                fb(6)

            fb(7)   fb(6)    fb(6)     fb(5)                  fb(6)     fb(5)                  fb(5)     fb(4)

………………………………………………………………………………………………………………………………………………        

不太会用这个……

看看上面有很多重复的子问题，如果数据量大的化那么就很浪费时间和空间了（递归的特点）

我们可以通过数组保存每一个子问题的值，再下一次使用直接从数组中取，这样保证了每个子问题的值只算了一次。（这是简单 的动态规划，看看博客）

代码如下：

注意事项:

参考代码:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cctype>
#include <cstring>
#include <string>
#include <stack> 
#include <algorithm>
#include <functional>
using namespace std;
int d[1001]={1,1}, n;
int dp(int i)
{
	if(d[i] > 0)
	{
		return d[i];
	}
	else
	{
		return d[i] = dp(i-1)+dp(i-2);
	}
}
int main()
{
	scanf("%d", &n);
	dp(n);
	printf("%d\n", d[n]);
	return 0;
}