這道題主要涉及動態規劃,利用這個,就能很好解決這個問題。
原題
給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額,返回 -1。
示例 1:
<code>輸入:
coins
=
[1,
2
,
5
],
amount
=
11
輸出:
3
解釋:
11
=
5
+
5
+
1
/<code>
示例 2:
<code>輸入: coins = [2], amount = 3
輸出: -1
/<code>
說明:
你可以認為每種硬幣的數量是無限的。
原題url:
https://leetcode-cn.com/problems/coin-change/
解題
求出所有可能
我們可以從小到大,求出由當前硬幣,組成所有金額的最小數,這樣最終就是最大金額所能組成的最小硬幣數量。
這種方法核心思想就是記錄所有中間狀態的結果,如果在實際使用中,你的傳入參數amount是不斷變化的,那麼用這種方法會比較方法,因為之前的結果可以被重複利用,這樣也是一種優勢。
現在我們來看看代碼:
<code>class
Solution
{public
int
coinChange
(
int
[] coins,int
amount) { Arrays.sort(coins);int
[] result =new
int
[amount +1
]; result[0
] =0
;for
(int
currentAmount =1
; currentAmount <= amount; currentAmount++) {int
minNum = Integer.MAX_VALUE;for
(int
j =0
; j < coins.length; j++) {int
remainAmount = currentAmount - coins[j];if
(remainAmount0
) {break
; }if
(result[remainAmount] == Integer.MAX_VALUE) {continue
; } minNum = Math.min(minNum, result[remainAmount] +1
); } result[currentAmount] = minNum; }return
result[amount] == Integer.MAX_VALUE ?-1
: result[amount]; } }/<code>
提交OK,執行用時:12 ms,內存消耗:36 MB,只超過了83.24%的 java 提交,看來還有優化的空間。
動態規劃優化
倒不是說動態規劃就一定比上面的方法更加優秀,只是也是一種思想,可以利用 dfs(深度優先搜索) 或者 bfs(廣度優先搜索),我下面這種寫法是 dfs,因為是一路進行到底之後,再去考慮其他情況的。(補充一點,如果使用 bfs 的話,可以藉助隊列來實現非遞歸的形式。)
所謂的優化,就是從硬幣的使用上來說,從面值大的開始,並且從可以使用數量最大的開始。與此同時,我們也記錄了最小使用數量,如果用當前面值最大的硬幣並且使用最多時,依舊大於最小值,那麼就不用繼續查找了。
以上的優化,其實是和題目相關聯,雖然不能用在其他的題目上,但也可以作為一種思想,值得我們借鑑和學習。
接下來我們看看代碼:
<code>class
Solution
{private
int
minCount = Integer.MAX_VALUE;public
int
coinChange
(
int
[] coins,int
amount) { Arrays.sort(coins); helper(coins, coins.length -1
,0
, amount);return
minCount == Integer.MAX_VALUE ?-1
: minCount; }private
void
helper
(
int
[] coins,int
coinIndex,int
curCount,int
amount) {if
(coinIndex0
) {return
; }if
(amount % coins[coinIndex] ==0
) { minCount = Math.min(minCount, curCount + amount / coins[coinIndex]);return
; }for
(int
i = amount / coins[coinIndex]; i >=0
; i--) {if
(curCount + i +1
>= minCount) {break
; } helper(coins, coinIndex -1
, curCount + i, amount - i * coins[coinIndex]); } } }/<code>
提交OK,執行用時:2 ms,內存消耗:34.7 MB,超過了100.00%的 java 提交,有種又快又好的感覺。
總結
以上就是這道題目我的解答過程了,不知道大家是否理解了。這道題主要利用動態規劃就可以解決,優化的時候需要注意邊界條件,從大到小取值,在時間複雜度上能更加優化。
有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號,說不定會有意外的驚喜。
https://death00.github.io/
公眾號:健程之道
關鍵字: coinIndex currentAmount MAX