518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

class Solution {
    public int change(int amount, int[] coins) {
        // dp[i][j] = combinations that make up amount j with first i coins;
        // base case dp[i][0]=1;
        // dp[i][j] = dp[i-1][j]+dp[i][j-coin[i-1]]);
        
        int[][] memo= new int[coins.length+1][amount+1];
        memo[0][0] = 1;
        for(int i =1; i<=coins.length; i++){
            memo[i][0]=1;
            for(int j=1; j<=amount; j++){
                memo[i][j]+=memo[i-1][j];
                if (j-coins[i-1]>=0) memo[i][j]+=memo[i][j-coins[i-1]];
            }           
        }
        return memo[coins.length][amount];
    }
}

memory optimized

class Solution {
    public int change(int amount, int[] coins) {
        int[] memo = new int[amount+1];
        memo[0] =1;
        for (int coin : coins){
            for (int j=coin; j<=amount; j++){
                // memo[j] = dpp[i-1][j]
                memo[j] += memo[j-coin] ;
            }
        }
        return memo[amount];
    }
}