题目描述

给定数组arr，设数组长度为n，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，代表要找的钱数，求换钱的方法数有多少种。由于方法的种数比较大，所以要求输出对10^9+7109+7进行取模后的答案。

输入描述:

输出包括两行，第一行包括两个整数n(0≤n≤1000)和aim(0≤aim≤20000)。第二行包含n个整数，表示arr数组(1≤arr[i]​≤1e9)。

输出描述:

输出一个整数，表示换钱的方法数。

#include<iostream>
#include<vector>using namespace std;
int process1(vector<int> arr, int index, int aim){int res = 0;if(index == arr.size()){res = aim == 0 ? 1 : 0;}else{for(int i=0; arr[index]*i<=aim; i++){res+=process1(arr, index+1, aim-arr[index]*i);}}return res;}int coins1(vector<int> arr, int aim){//暴力递归if(arr.empty() || aim<=0){return 0;}return process1(arr, 0, aim);}
int process2(vector<int> &arr, int index, int aim, vector<vector<int>> &m){int res=0;if(index == arr.size()){res = aim ==0 ? 1:0;}else{int mapValue = 0;for(int i=0;arr[index]*i<=aim;i++){mapValue = m[index+1][aim-arr[index]*i];if(mapValue!=0){res += mapValue == -1?0:mapValue;}else{res += process2(arr, index+1, aim-arr[index]*i, m);}}}m[index][aim] = res == 0?-1:res;//m[i][j]=-1表示递归过程p(i,j)计算过，但是返回值为0return res;
}
int coins2(vector<int> &arr, int aim){//记忆化搜索if(arr.empty() || aim<=0){return 0;}vector<vector<int>> map(arr.size()+1, vector<int> (aim+1, 0));return process2(arr, 0, aim, map);
}
int coins3(vector<int> arr, int aim){//动态规划int n = arr.size();vector<vector<int>> dp(n,vector<int>(aim+1));for(int row = 0;row < n; row++){dp[row][0] = 1;}for(int j = 1; arr[0]*j <= aim;j++){dp[0][arr[0]*j]=1;}int num = 0;for(int i=1;i<n;i++){for(int j = 1;j<=aim; j++){num = 0;for(int k = 0;j-arr[i]*k >= 0; k++){num += dp[i-1][j-arr[i]*k];}dp[i][j]=num;}}return dp[n-1][aim];
}int coins4(vector<int> arr, int aim){//O(N X aim)时间复杂度的动态规划if(arr.empty()||aim<0) return 0;int n = arr.size();vector<vector<int>> dp(n,vector<int>(aim+1));for(int row = 0;row < n; row++){dp[row][0] = 1;}for(int j = 1; arr[0]*j <= aim;j++){dp[0][arr[0]*j]=1;}int num = 0;for(int i=1;i<n;i++){for(int j = 1;j<=aim; j++){dp[i][j] = dp[i-1][j];dp[i][j] += j-arr[i] >= 0 ? dp[i][j-arr[i]] : 0;}}return dp[n-1][aim];
}
int coins5(vector<int> arr, int aim){//O(N X aim)时间复杂度,O(aim)空间复杂度的动态规划if(arr.empty()||aim<0) {return 0;}int n = arr.size();vector<int> dp(aim+1, 0);dp[0]=1;for(int j = 1; arr[0]*j <= aim;j++){dp[arr[0]*j]=1;}for(int i=1;i<n;i++){for(int j = 1;j<=aim; j++){dp[j] += j-arr[i] >= 0 ? dp[j-arr[i]] : 0;}}return dp[aim];
}
int main(){/*int n, aim;cin>>n>>aim;vector<int> arr(n, 0);cout<<coins1(arr, aim)<<endl;*/vector<int> arr={2, 3, 5, 7, 10};cout<<coins5(arr, 1000)<<endl;system("pause");return 0;
}