image.png
问题分析：完全背包问题，且求的是最值，并且需要达到恰好装满容量为amount的背包。

解法一（最朴素）

注：由于没有进行下标填充，所以初始化过程需要特殊处理

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         int[][] dp = new int[n][amount + 1];
  5.         int INF = 0x3f3f3f;
  6.         //初始化
  7.         for(int i = 0; i < n; i++){
  8.             Arrays.fill(dp[i], INF);
  9.         }
  10.         //特殊处理 coins[0]物品的情况
  11.         dp[0][0] = 0;
  12.         for(int j = 1; j <= amount; j++){
  13.             dp[0][j] = j % coins[0] == 0 ? j / coins[0] : INF;
  14.         }
  16.         for(int i = 1; i < n; i++){
  17.             int val = coins[i];
  18.             for(int j = 0; j <= amount; j++){
  19.                 for(int k = 0; k * val <= j; k++){
  20.                     dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * val] + k);
  21.                 }
  22.             }
  23.         }
  24.         return dp[n-1][amount] == INF ? -1 : dp[n-1][amount];
  25.     }
  26. }

解法二（下标填充）

注：进行下标填充，初始化的过程简化了

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int n = coins.length;
  4.         int[][] dp = new int[n + 1][amount + 1];
  5.         int INF = 0x3f3f3f;
  6.         for(int i = 0; i <= n; i++){
  7.             Arrays.fill(dp[i], INF);
  8.         }
  9.         dp[0][0] = 0;
  11.         for(int i = 1; i <= n; i++){
  12.             int val = coins[i - 1];
  13.             for(int j = 0; j <= amount; j++){
  14.                 for(int k = 0; k * val <= j; k++){
  15.                     dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * val] + k);
  16.                 }
  17.             }
  18.         }
  19.         return dp[n][amount] == INF ? -1 : dp[n][amount];
  20.     }
  21. }

解法三（一维）

注：完全背包的二维解法到一维解法，可以降低时间复杂度，一维解法的时间复杂度为O(N * C)

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        int INF = 0x3f3f3f;

        Arrays.fill(dp, INF);
        dp[0] = 0;

        for(int i = 1; i <= n; i++){
            int val = coins[i - 1];
            for(int j = 0; j <= amount; j++){
                int a = dp[j];
                int b = j - val >= 0 ? dp[j - val] + 1 : INF;
                dp[j] = Math.min(a, b);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}