> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/dynamic-programming/knapsack-problems.md).

# Knapsack Problems

## KnapSack 背包问题

[*518 Coin Change 2*](https://leetcode.com/problems/coin-change-2/description/)

```java
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];
}
```