【牛牛的超市】
目录
- 牛课题霸：牛牛的超市
牛课题霸：牛牛的超市 牛牛最近在家闲的无聊，所以决定在家开一个小超市，为了方便卖东西，牛牛发明了一种用来兑换东西的新型货币，牛牛给这种新型货币起了个名字叫牛币，现在牛牛有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个，现在牛妹来到牛牛的超市买东西，牛妹有 x(x<=100) 元牛币，但是牛妹想将 x 元牛币换成若干零钱，请问有多少种换钱的方案？
输入
3，6，[ [1, 100],[2, 100], [5, 100] ]
说明：
表示有3种货币，要兑换的金额是6元，
第一种货币面额1，有100张
第二种货币面额2，有100张
第二种货币面额5，有100张
输出使用动态规划算法求解
5
| n\x | 0元 | 1元 | 2元 | 3元 | 4元 | 5元 | 6元 |
|---|---|---|---|---|---|---|---|
| 0元/币 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1元/币 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2元/币 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
| 5元/币 | 1 | 1 | 2 | 2 | 3 | 4 | 5 |
dp[0][0] = 1
class Solution {
public:
/**
*
* @param n int整型 ：牛币值种类数
* @param x int整型 ：牛妹拥有的钱数
* @param a int整型vector> ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
* @return int整型
*/
int solve(int n, int x, vector >& a) {
// write code here
int dp[n+1][x+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1;
i <= n;
i++)
for(int j = 0;
j <= x;
j++)
/*
* 当第i种货币取k个时，剩下的钱换其他货币有dp[i-1][j - k*a[i-1][0]]种方案
*/
for(int k = 0;
k <= a[i-1][1];
k++)
if(j - k*a[i-1][0] >= 0) {
dp[i][j] += dp[i-1][j - k*a[i-1][0]];
} else {
break;
}
return dp[n][x];
}
};
