题目：现有1元、5元、10元、20元、50元面值不等的钞票，问需要90元钱有多少种找钱方案

此题如果没要求打印结果，只要求打印出一共有多少种方案，那么可以采用贪心算法

首先选取最大的，然后逐次选择最小的进行递归实现

代码如下：

#include "stdafx.h"

#include <iostream>

#include <stdio.h>

using namespace std;

int arr[5]={50,20,10,5,1};

int fun( int n,int index) {

if(n<0) return 0;

if(n==0)return 1;

int num=0;

if(index==5) return 0;

for(int i=0;i<=n/arr[index];i++)

{

num+=fun(n-i*arr[index],index+1);

}

return num;

}

int _tmain(int argc, _TCHAR* argv[])

{

cout<<fun(1,0)<<endl;

cout<<fun(5,0)<<endl;

cout<<fun(10,0)<<endl;

cout<<fun(90,0)<<endl;

system("pause");

return 0;

}