生活随笔
收集整理的這篇文章主要介紹了
LeetCode 322. 零钱兑换（DP）
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
文章目錄
- 1. 題目信息
- 2. 解題
- 2.1 回溯窮舉
- 2.2 動態(tài)規(guī)劃
1. 題目信息
給定不同面額的硬幣 coins 和一個(gè)總金額 amount。
編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。
如果沒有任何一種硬幣組合能組成總金額，返回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1示例 2:
輸入: coins = [2], amount = 3
輸出: -1說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的。
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/coin-change
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
2. 解題
類似題目：LeetCode 518. 零錢兌換 II（動態(tài)規(guī)劃）
2.1 回溯窮舉
超時(shí)
class Solution
{
public:int coinChange(vector
<int>& coins
, int amount
){int minPieces
= INT_MAX
;money(coins
, amount
, 0, 0, minPieces
);if(minPieces
!= INT_MAX
)return minPieces
;elsereturn -1;}void money(vector
<int>& coins
, int &amount
, long curMoney
, int curPieces
, int &minPieces
){if(curMoney
> amount
){curPieces
= INT_MAX
;return;}if(curMoney
== amount
){if(curPieces
< minPieces
)minPieces
= curPieces
;return;}for(int i
= 0; i
< coins
.size(); ++i
){money(coins
, amount
,curMoney
+coins
[i
], curPieces
+1, minPieces
)；
}}
};
2.2 動態(tài)規(guī)劃
states[i]表示找 i 元需要的最少張數(shù)
那么states[i] = min{states[i-coins[j]] | j = 0,1,…coins.size() }+1
class Solution {
public:int coinChange(vector
<int>& coins
, int amount
) {if(amount
< 1)return 0;int states
[amount
+1];int i
, j
;for(i
= 0; i
<= amount
; ++i
)states
[i
] = amount
+1;states
[0] = 0;for(i
= 0; i
<= amount
; ++i
){for(j
= 0; j
< coins
.size(); ++j
){if(i
-coins
[j
] >= 0 && states
[i
] > states
[i
-coins
[j
]]+1){states
[i
] = states
[i
-coins
[j
]]+1;}}}if(states
[amount
] != amount
+1)return states
[amount
];elsereturn -1;}
};
class Solution {
public:int coinChange(vector
<int>& coins
, int amount
) {if(amount
<= 0)return 0;int n
= coins
.size(), j
, m
;vector
<int> dp(amount
+1, INT_MAX
);dp
[0] = 0;for(j
= 0; j
<= amount
; ++j
){if(dp
[j
] != INT_MAX
){for(m
= 0; m
< n
; ++m
){if(j
<= amount
-coins
[m
])dp
[j
+coins
[m
]] = min(dp
[j
]+1, dp
[j
+coins
[m
]]);}}}if(dp
[amount
] != INT_MAX
)return dp
[amount
];return -1;}
};
總結(jié)
以上是生活随笔為你收集整理的LeetCode 322. 零钱兑换（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
