leetcode - 518. Change II

leetcode - 518. Change for II

subject

Code

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

int change(int amount, vector<int>& coins) {
    
	vector<int> dp(amount+1);
	dp[0] = 1; //  The amount of money is 0 when , Means you don't take any change , So it is 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;
}