一、貨幣問題I

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算並返回可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

leetcode

1、分析

從左往右的嘗試模型，每種貨幣都嘗試，用0張、用1張、用2張...，最後求min就是組成aim（amount）的最少貨幣數

2、實現

2.1、暴力遞歸

暴力實現測試會超時，但思路是對的，需要進一步優化。

public static int coinChange(int[] coins, int amount) {
    int ans = process(coins, 0, amount);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

// arr[index...]面值，每種面值張數自由選擇，
// 搞出rest正好這麼多錢，返回最小張數
// 拿Integer.MAX_VALUE標記怎麼都搞定不了
private static int process(int[] arr, int index, int rest) {
    // 當前index來到數組越界位置，如果剩餘rest等於0，說明本次貨幣不需要用，前邊已經搞定了
    if (index == arr.length) { // base case 
        return rest == 0 ? 0 : Integer.MAX_VALUE;
    } 
    int ans = Integer.MAX_VALUE;
    for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
        int next = process(arr, index + 1, rest - zhang * arr[index]);
        if (next != Integer.MAX_VALUE) {
            ans = Math.min(ans, zhang + next);
        }
    }
    return ans;
}

2.2、dp（填表）

由暴力遞歸改動態規劃，通過遞歸分析得出index位置依賴於index+1，所以從下往上推，填格子

public static int coinChange(int[] coins, int amount) {
  int ans = dp(coins, amount);
  return ans == Integer.MAX_VALUE ? -1 : ans;
}

public static int dp(int[] arr, int aim) {
  if (aim == 0) {
      return 0;
  }
  int N = arr.length;
  int[][] dp = new int[N + 1][aim + 1];
  dp[N][0] = 0;
  for (int j = 1; j <= aim; j++) {
      dp[N][j] = Integer.MAX_VALUE;
  }
  for (int index = N - 1; index >= 0; index--) {
      for (int rest = 0; rest <= aim; rest++) {
          int ans = Integer.MAX_VALUE;
          for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
              int next = dp[index + 1][rest - zhang * arr[index]];
              if (next != Integer.MAX_VALUE) {
                  ans = Math.min(ans, zhang + next);
              }
          }
          dp[index][rest] = ans;
      }
  }
  return dp[0][aim];
}

2.3、dp（斜率優化）

發現有枚舉行為的動態規劃，可以進一步優化，把最內層的for循環去掉，觀察臨近位置，看哪些位置能替換枚舉行為，變成幾個有限位置做決策，在dp中可以認為這種操作為斜率優化。

public static int coinChange(int[] coins, int amount) {
    int ans = dp(coins, amount);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

public static int dp(int[] arr, int aim) {
    if (aim == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 0;
    for (int j = 1; j <= aim; j++) {
        dp[N][j] = Integer.MAX_VALUE;
    }
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            dp[index][rest] = dp[index + 1][rest];
            if (rest - arr[index] >= 0
                && dp[index][rest - arr[index]] != Integer.MAX_VALUE) {
                dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - arr[index]] + 1);
            }
        }
    }
    return dp[0][aim];
}

二、貨幣問題II

給你一個整數數組 coins 表示不同面額的硬幣，另給一個整數 amount 表示總金額。

請你計算並返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回 0 。

假設每一種面額的硬幣有無限個。

題目數據保證結果符合 32 位帶符號整數。

示例 1：

輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

輸入：amount = 3, coins = [2]
輸出：0
解釋：只用面額 2 的硬幣不能湊成總金額 3 。

示例 3：

輸入：amount = 10, coins = [10] 
輸出：1

提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值互不相同
0 <= amount <= 5000

leetcode

1、分析

從左往右的嘗試模型：每種貨幣用0張，用1張，用2張......

2、實現

2.1、暴力遞歸

暴力實現測試會超時，但思路是對的，需要進一步優化。

public int change(int amount, int[] coins) {
    return coinsWay(coins, amount);
}

public static int coinsWay(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    return process(arr, 0, aim);
}

// arr[index....] 所有的面值，每一個面值都可以任意選擇張數，組成正好rest這麼多錢，方法數多少？
private static int process(int[] arr, int index, int rest) {
    if (index == arr.length) { // base case 沒錢了
        return rest == 0 ? 1 : 0;
    }
    int ways = 0;
    for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
        ways += process(arr, index + 1, rest - (zhang * arr[index]));
    }
    return ways;
}

2.2、dp（填表）

由暴力遞歸改動態規劃，通過遞歸分析得出index位置依賴於index+1，所以從下往上推，填格子

public int change(int amount, int[] coins) {
    return dp(coins, amount);
}

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ways = 0;
            for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                ways += dp[index + 1][rest - (zhang * arr[index])];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}

2.3、dp（斜率優化）

發現有枚舉行為（最內層for循環），可進一步通過觀察鄰近位置進行斜率優化

public int change(int amount, int[] coins) {
    return dp(coins, amount);
}

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            dp[index][rest] = dp[index + 1][rest];
            if (rest - arr[index] >= 0) {
                dp[index][rest] += dp[index][rest - arr[index]];
            }
        }
    }
    return dp[0][aim];
}

三、貨幣問題III

arr是貨幣數組，其中的值都是正數。再給定一個正數aim。

每個值都認為是一張貨幣，

認為值相同的貨幣沒有任何不同，

返回組成aim的方法數

例如：arr = {1,2,1,1,2,1,2}，aim = 4

方法：1+1+1+1、1+1+2、2+2

一共就3種方法，所以返回3

1、分析

貨幣問題II中的貨幣是無限張，此題的貨幣張數是有限的，這是關鍵點

統計不同面值的貨幣出現的次數

2、實現

2.1、暴力遞歸

public static class Info {
    public int[] coins; // 貨幣數組
    public int[] zhangs; // 張數數組

    public Info(int[] c, int[] z) {
        coins = c;
        zhangs = z;
    }
}

public static int coinsWay(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr); // 統計不同貨幣的張數信息
    return process(info.coins, info.zhangs, 0, aim);
}

// coins 面值數組，正數且去重
// zhangs 每種面值對應的張數
private static int process(int[] coins, int[] zhangs, int index, int rest) {
    if (index == coins.length) {
        return rest == 0 ? 1 : 0;
    }
    int ways = 0;
    for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
        ways += process(coins, zhangs, index + 1, rest - (zhang * coins[index]));
    }
    return ways;
}

private static Info getInfo(int[] arr) {
    // key：貨幣面值，value：貨幣張數
    HashMap<Integer, Integer> counts = new HashMap<>();
    for (int value : arr) {
        if (!counts.containsKey(value)) {
            counts.put(value, 1);
        } else {
            counts.put(value, counts.get(value) + 1);
        }
    }
    int N = counts.size();
    int[] coins = new int[N];
    int[] zhangs = new int[N];
    int index = 0;
    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
        coins[index] = entry.getKey();
        zhangs[index++] = entry.getValue();
    }
    return new Info(coins, zhangs);
}

2.2、dp（填表）

根據暴力遞歸改動態規劃

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] zhangs = info.zhangs;
    int N = coins.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ways = 0;
            for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
                ways += dp[index + 1][rest - (zhang * coins[index])];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}

2.3、dp（斜率優化）

發現有內層for循環，畫圖找鄰居位置，得出依賴關係，進一步斜率優化，省掉內層for循環

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    Info info = getInfo(arr);
    int[] coins = info.coins;
    int[] zhangs = info.zhangs;
    int N = coins.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            dp[index][rest] = dp[index + 1][rest];
            if (rest - coins[index] >= 0) {
                dp[index][rest] += dp[index][rest - coins[index]];
            }
            if (rest - coins[index] * (zhangs[index] + 1) >= 0) {
                dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)];
            }
        }
    }
    return dp[0][aim];
}

四、貨幣問題IV

arr是貨幣數組，其中的值都是正數。再給定一個正數aim。

每個值都認為是一張貨幣，

即便是值相同的貨幣也認為每一張都是不同的，

返回組成aim的方法數

例如：arr = {1,1,1}，aim = 2

第0個和第1個能組成2，第1個和第2個能組成2，第0個和第2個能組成2

一共就3種方法，所以返回3

1、分析

貨幣問題III是值相同的貨幣沒有任何不同，而此題值相同的貨幣認為是不同的，這是這道題的關鍵。

2、實現

2.1、暴力遞歸

先用暴力解求出，再進一步優化

從左往右的嘗試模型：每張貨幣要不要問題

public static int coinWays(int[] arr, int aim) {
    return process(arr, 0, aim);
}

// arr[index....] 組成正好rest這麼多的錢，有幾種方法
private static int process(int[] arr, int index, int rest) {
    if (rest < 0) {
        return 0;
    }
    if (index == arr.length) { // 沒錢了！
        return rest == 0 ? 1 : 0;
    } 
    // 可能性一：要當前貨幣
    // 可能性二：不要當前貨幣
    return process(arr, index + 1, rest) + process(arr, index + 1, rest - arr[index]);
}

2.2、dp（填表）

根據暴力遞歸改動態規劃，沒有枚舉行為，填好dp格子就是最優解

填表：index位置依賴index+1位置，所以從下往上填，從左往右填

public static int dp(int[] arr, int aim) {
    if (aim == 0) {
        return 1;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            dp[index][rest] = dp[index + 1][rest] + (rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : 0);
        }
    }
    return dp[0][aim];
}

小夥伴們有興趣想了解內容和更多相關學習資料的請點讚收藏+評論轉發+關注我，後面會有很多乾貨。我有一些面試題、架構、設計類資料可以說是程式設計師面試必備！

所有資料都整理到網盤了，需要的話歡迎下載！私信我回復【111】即可免費獲取

出處：https://mdnice.com/user/169389355945

內卷大廠系列《貨幣問題四連擊》

一、貨幣問題I

1、分析

2、實現

2.1、暴力遞歸

2.2、dp（填表）

2.3、dp（斜率優化）

二、貨幣問題II

1、分析

2、實現

2.1、暴力遞歸

2.2、dp（填表）

2.3、dp（斜率優化）

三、貨幣問題III

1、分析

2、實現

2.1、暴力遞歸

2.2、dp（填表）

2.3、dp（斜率優化）

四、貨幣問題IV

1、分析

2、實現

2.1、暴力遞歸

2.2、dp（填表）