Leetcode June Challenge - Day 7

Problem: LeetCode June Challenge - Day 7

Ideas:

  1. This is a very standard dp problem. dp(amount, nfirstcoins) = dp(amount-coins[nfirstcoins], nfirstcoins) + dp(amount, nfirstcoins - 1). Sum both possibilities, since we want the number of ways.

Solution:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        int dp[amount+1][n+1];
        
        for(int i=0; i<=n; ++i) dp[0][i] = 1;
        for(int i=1; i<=amount; ++i) dp[i][0] = 0;
        
        for(int i=1; i<=amount; ++i)
            for(int j=1; j<=n; ++j){
                dp[i][j] = dp[i][j-1];
                if(i >= coins[j-1])
                    dp[i][j] += dp[i-coins[j-1]][j];
            }
        
        
        return dp[amount][n];
    }
};