Coin Change II

1public int change(int amount, int[] coins) {
2    int n = coins.length;
3    int[][] dp = new int[n + 1][amount + 1];
4
5    // Base case: one way to make 0
6    for (int i = 0; i <= n; i++) {
7        dp[i][0] = 1;
8    }
9
10    for (int i = 1; i <= n; i++) {
11        int coin = coins[i - 1];
12        for (int j = 1; j <= amount; j++) {
13            // Ways without using current coin
14            dp[i][j] = dp[i - 1][j];
15
16            // Add ways using current coin
17            if (j >= coin) {
18                dp[i][j] += dp[i][j - coin];
19            }
20        }
21    }
22
23    return dp[n][amount];
24}