完全背包问题

这个问题转化为背包问题的描述形式：

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

若只使用 coins 中的前 i 个硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。

如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。

public int change(int amount, int[] coins) {
       int n = coins.length;
       int[][] dp = new int[n + 1][amount + 1];
       // base case
       for (int i = 0; i <= n; i++)
           dp[i][0] = 1;

       for (int i = 1; i <= n; i++) {
           for (int j = 1; j <= amount; j++)
               if (j - coins[i - 1] >= 0)
                   dp[i][j] = dp[i - 1][j]
                           + dp[i][j - coins[i - 1]];
               else
                   dp[i][j] = dp[i - 1][j];
       }
       return dp[n][amount];
   }