322. Coin Change
Leetcode
https://leetcode.com/problems/coin-change/description/
題目
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1Example 2:
Input: coins = [2], amount = 3
Output: -1Example 3:
Input: coins = [1], amount = 0
Output: 0解答
方法一
一開始的想法是將 amount 當做 DP 不斷累加的對象
範例：coins = [1, 6, 7, 11], amount = 13
一開始設初始值 dp = [0]，dp[index] 代表擲到 index 數字所需的最小次數，dp[0] 意思是擲到 0 所需的次數為零 (不需要擲)，接著從 1 遍歷到 amount: 13，計算每一輪中擲出 amount 的最低次數：
amount: 1 時，直接取第一個元素即可，最低次數為 1 => dp = [0, 1]
amount: 2 時，最低次數會是 dp[1] + dp[1]，代表擲出兩次 1
最低次數為 2 => dp = [0, 1, 2]
amount: 3 時，最低次數會是 dp[2] + dp[1]，代表擲出三次 1
最低次數為 3 => dp = [0, 1, 2, 3]
...
amount: 6 時，直接取第二個元素，代表擲出一次 6 => dp[6] = 1
amount: 7 時，直接取第三個元素，代表擲出一次 7 => dp[7] = 1
...
amount: 13 時，最低次數有可能會是：
先看 coins 中有沒有 13，有的話那就代表擲出一次 13 即可 => dp[13] = 1
接著最低次數的判斷可以根據之前計算出來的 DP 結果找出來：
dp[1] + dp[12]=> 代表擲出 1 的最低次數 + 擲出 12 的最低次數dp[2] + dp[11]=> 代表擲出 2 的最低次數 + 擲出 11 的最低次數...
dp[6] + dp[7]=> 代表擲出 6 的最低次數 + 擲出 7 的最低次數
最後發現 dp[6] + dp[7] 是最低的擲出次數 2 => 所以 dp[13] = 2，代表擲出 13 的最低次數為 2
var coinChange = function (coins, amount) {
if (amount === 0) return 0;
const dp = [0];
for (let i = 1; i <= amount; i++) {
const target = coins.find(coin => coin === i);
if (target) {
// 元素存在，擲一次就可以
dp[i] = 1;
} else {
// 如果元素不存在，先把 dp[i] 設為最大值
dp[i] = Number.MAX_SAFE_INTEGER;
let match = false;
// 遍歷前面 dp 的可能性
for (let j = 1; j <= Math.floor(i / 2); j++) {
if (dp[j] !== -1 && dp[i - j] !== -1) {
// 遍歷前面 dp 的可能性，找出最小擲出的次數
dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
match = true;
}
}
// 怎麼擲都擲不出來的狀況設為 -1
if (!match) {
dp[i] = -1;
}
}
}
return dp[amount];
};但這個方法會從 1 一路算到 amount，並且每一輪中還要遍歷原有的 dp 找出最小值，所以很明顯會 TLE
時間複雜度：O(n^2)
一開始 amount 要先遍歷一次(n)，接著乘以 遍歷前面 dp 的可能性 中的迴圈 (n)
方法二
上面會 TLE 的主要原因在於遍歷 amount 的每一輪中都要遍歷前面 dp，時間複雜度會達到 n^2
for (let j = 1; j <= Math.floor(i / 2); j++) {
...
}如果 coins = [71,440,63,321,461,310,467,456,361], amount = 9298，因為 amount 的數字很大，採用方法一的方式很明顯會超時，所以我們必須換一個想法來找出 dp 的狀態轉移方程：
範例：coins = [1, 6, 7, 11], amount = 13
目標是求得 dp[13] 的話，可以先遍歷 coins 再求得各 dp 的值，例如：
coins[0] = 1假設先擲出 1 的狀況，那麼
dp[13] = 1 (擲出 1 的一次) + dp[12]coins[1] = 6假設擲出 6 的狀況，那麼
dp[13] = 1 (擲出 6 的一次) + dp[7]coins[2] = 7假設擲出 7 的狀況，那麼
dp[13] = 1 (擲出 7 的一次) + dp[6]coins[3] = 11假設擲出 11 的狀況，那麼
dp[13] = 1 (擲出 11 的一次) + dp[2]
這樣其實我們就找出了 dp 的規律，dp[13] 最低的擲出次數就是以上四種狀況的最小值
而各 dp 的值也可以根據上面的這個規律求出來：
coins[0] = 1, amount = 1擲出 1 的狀況，那麼
dp[1] = 1 (擲出 1 的一次) + dp[1 - 1]=>
dp[1] = 1，代表擲出一次 1coins[0] = 1, amount = 2擲出 1 的狀況，那麼
dp[2] = 1 (擲出 1 的一次) + dp[2 - 1] = 1 + 1=>
dp[2] = 2，代表擲出兩次 1...
...
coins[1] = 6, amount = 7擲出 6 的狀況，那麼
dp[7] = 1 (擲出 6 的一次) + dp[7 - 6] = 1 + 1=>
dp[7] = 2，代表擲出一次 6 + 一次 1coins[1] = 6, amount = 8擲出 6 的狀況，那麼
dp[8] = 1 (擲出 6 的一次) + dp[8 - 6] = 1 + 2=>
dp[8] = 3，代表擲出一次 6 + 兩次 1
依照上面的規律寫出如下的程式碼：
var coinChange = function (coins, amount) {
if (amount === 0) return 0;
const dp = [0];
// 先遍歷 amount
for (let i = 1; i <= amount; i++) {
// 因為 dp 判斷會取最小值，初始值要設為最大值
dp[i] = Number.MAX_SAFE_INTEGER;
// 再遍歷 coins
for (let j = 0; j < coins.length; j++) {
const coin = coins[j];
// 如果 coin 小於當前的 amount，代表可以擲出來 (ex. coin = 2, i = 3)
if (coin <= i) {
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
// 如果 dp[amount] 一樣是最大值，代表擲不出來
return dp[amount] === Number.MAX_SAFE_INTEGER ? -1: dp[amount];
};時間複雜度：O(m x n) - amount * coins
參考資料
Last updated
Was this helpful?