leetcode - 518. 零钱兑换 II

题目

代码

#include <iostream>
#include <vector>
using namespace std;

int change(int amount, vector<int>& coins) {
    
	vector<int> dp(amount+1);
	dp[0] = 1; // 钱数为0时，表示任何零钱也不拿，所以是1
	for(int i = 0; i < coins.size(); i++){
    
		int coin = coins[i];
		for(int j = coin; j <= amount; j++){
    
			dp[j] += dp[j-coin];
		}
	} 
	return dp[amount];
}

int main(){
    
	int n, amount, res;
	cin>>n>>amount;
	vector<int> coins(n);
	for(int i = 0; i < n; i++){
    
		cin>>coins[i];
	}
	res = change(amount, coins);
	cout<<res;
    return 0;
}