题目：给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim代表要找的钱数，求换钱有多少种方法。代码如下：

　　

1 #include
     
        2 #include
      
         3 using namespace std;  4 //动态规划  5 class Exchange {  6 public:  7     int countWays(vector
       
         penny, int n, int aim)   8     {  9         if(n==0||aim<0) 10             return 0; 11         int **map=new int*[n]; 12         for(int i=0;i
        
         =0) 27                     map[i][j]=map[i][j-penny[i]]+map[i-1][j]; 28                 else 29                     map[i][j]=map[i-1][j]; 30         return map[n-1][aim]; 31     } 32  33 }; 34  35  36 /*记忆搜索 37 class Exchange { 38 public: 39     int countWays(vector
         
           penny, int n, int aim)  40     { 41         if(n==0||aim<0) 42             return 0; 43         int **map=new int*[n]; 44         for(int i=0;i
          

arr,int index,int aim,int **map) 53 { 54 int res; 55 if(arr.size()-1==index) 56 { 57 if(map[index][aim]==-1) 58 map[index][aim]=(aim%arr[index])?0:1; 59 return map[index][aim]; 60 } 61 else 62 { 63 res=0; 64 int k=aim/arr[index]; 65 for(int i=0;i<=k;i++) 66 { 67 if(map[index+1][aim-i*arr[index]]==-1) 68 map[index+1][aim-i*arr[index]]=process(arr,index+1,aim-i*arr[index],map); 69 res+=map[index+1][aim-i*arr[index]]; 70 } 71 } 72 return res; 73 } 74 };*/ 75 76 /*暴力搜索 77 class Exchange { 78 public: 79 int countWays(vector

penny, int n, int aim) 80 { 81 if(n==0||aim<0) 82 return 0; 83 return process(penny,0,aim); 84 85 } 86 int process(vector

arr,int index,int aim) 87 { 88 int res; 89 if(arr.size()-1==index) 90 { 91 res=(aim%arr[index])?0:1; 92 return res; 93 } 94 else 95 { 96 res=0; 97 int k=aim/arr[index]; 98 for(int i=0;i<=k;i++) 99 res+=process(arr,index+1,aim-i*arr[index]);100 }101 return res;102 }103 };*/104 105 int main()106 {107 int a[3]={ 1,2,3};108 vector

arr(a,a+3);109 Exchange e;110 cout<