有数组penny,penny中所有的值都为正数且不重复。每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim(小于等于1000)代表要找的钱数,求换钱有多少种方法。
给定数组penny及它的大小(小于等于50),同时给定一个整数aim,请返回有多少种方法可以凑成aim。
测试样例:
输入:[1,2,4],3,3
返回:2
class Exchange {
public:
int countWays(vector<int> penny, int n, int aim) {
// write code here
vector< vector<int> > dp(n, vector<int> (aim+1, 0));
for(int i=0; i<n; i++){ dp[i][0] = 1; }
for(int j=1; j*penny[0] <= aim; ++j) { dp[0][j*penny[0]] = 1;}
for(int i=1; i<n; ++i){
for(int j=1; j<=aim; ++j){
dp[i][j] = dp[i-1][j] + (j-penny[i] >= 0 ? dp[i][j-penny[i]] : 0);
}
}
return dp[n-1][aim];
}
};