经典背包问题
从小往大推就不会有事
class Solution {
public:
int change(int amount, vector<int>& coins) {
int ans[5005];
memset(ans, 0, sizeof(ans));
ans[0] = 1;
for (int i = 0; i < coins.size(); i++)
for (int j = 0; j < amount; j++) {
if (j + coins[i] > amount)
break;
ans[j + coins[i]] += ans[j];
}
return ans[amount];
}
};
