Knapsack Problems

KnapSack 背包问题

518 Coin Change 2

public int change(int amount, int[] coins) {
    // dp[i][j] : the number of unique combinations to make up to i by using only the first j types of coin 
    int[][] dp = new int[coins.length + 1][amount + 1];
    dp[0][0] = 1;
    
    for (int i = 1; i <= coins.length; i++) {
        dp[i][0] = 1;
        for (int j = 0; j <= amount; j++) {
            dp[i][j] = dp[i-1][j] + (j >= coins[i - 1] ? dp[i][j - coins[i - 1]] : 0);
        }
    }
    
    return dp[coins.length][amount];
}