資訊專(zhuān)欄INFORMATION COLUMN
摘要：傳入的參數(shù)為手上有的紙幣的面額以及希望兌換的面額。這里假設(shè)紙幣的數(shù)量是無(wú)窮的。這題本質(zhì)上考察的是動(dòng)態(tài)規(guī)劃思想。這里有兩種動(dòng)態(tài)規(guī)劃的方法，分別從遞歸和非遞歸的角度解決這個(gè)問(wèn)題。具體的情況還是要看數(shù)據(jù)的分布情況來(lái)確定選擇哪種方法。
題目要求
You are given coins of different denominations and a total amount of money amount. Write a function to compute 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. Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1) Example 2: coins = [2], amount = 3 return -1. Note: You may assume that you have an infinite number of each kind of coin.
這里模擬實(shí)現(xiàn)了一個(gè)換錢(qián)算法。傳入的參數(shù)為手上有的紙幣的面額以及希望兌換的面額。這里假設(shè)紙幣的數(shù)量是無(wú)窮的。
這題本質(zhì)上考察的是動(dòng)態(tài)規(guī)劃思想。這里有兩種動(dòng)態(tài)規(guī)劃的方法，分別從遞歸和非遞歸的角度解決這個(gè)問(wèn)題。具體的情況還是要看數(shù)據(jù)的分布情況來(lái)確定選擇哪種方法。
非遞歸這里我們新建一個(gè)臨時(shí)數(shù)組result，下標(biāo)i上的值來(lái)存儲(chǔ)用當(dāng)前手上的紙幣兌換面額i時(shí)所需要的最少的紙幣數(shù)量。這樣，假設(shè)有一個(gè)紙幣數(shù)組[coin[0], coint[1], ..., coin[k]]，我們需要計(jì)算兌換面額i所需要的最小數(shù)量的紙幣，那么只需要比較[result[i-coin[0]], result[i-coin[1]], result[i-coin[2]] ... , result[i-coint[k]]]即可。這里需要考慮一些越界情況比如手上紙幣面額比需兌換面額大。還有可能result[i-coin[t]]是無(wú)法兌換的。
public int coinChange(int[] coins, int amount) {
if(amount==0) return 0;
Arrays.sort(coins);
if(coins==null || coins.length==0 || amount < coins[0]) return -1;
int[] result = new int[amount+1];
for(int i = coins[0] ; i<=amount; i++){
int tmp = Integer.MAX_VALUE;
for(int j = 0 ; j
遞歸
這里需要注意的是，用int數(shù)組作為一個(gè)緩存來(lái)減少重復(fù)計(jì)算的損耗。其實(shí)這里的代碼還是可以繼續(xù)優(yōu)化的。
private int[] cache;
public int coinChange2(int[] coins, int amount){
cache = new int[amount];
return coinChangeRecursive(coins, amount);
}
public int coinChangeRecursive(int[] coins, int amount){
if(amount<0) return -1;
if(amount==0) return 0;
if(cache[amount-1] != 0) return cache[amount-1];
int min = Integer.MAX_VALUE;
for(int coin : coins){
int res = coinChangeRecursive(coins, amount-coin);
if(res>=0 && res
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/68758.html
Problem You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount o...
摘要：解題思路動(dòng)態(tài)規(guī)劃，用表示總價(jià)為的最小紙幣張數(shù)，很容易想到狀態(tài)轉(zhuǎn)移方程當(dāng)然前提是要大于紙幣金額數(shù)。表示取一張面額加上合計(jì)為的最小紙幣數(shù)。另題目要求無(wú)法合計(jì)出的金額，要返回，所以要作特殊處理，否則就會(huì)返回元素初始化值代碼 Coin ChangeYou are given coins of different denominations and a total amount of money...
Problem You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infini...
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：原文鏈接歡迎現(xiàn)在有塊錢(qián)人民幣，將塊錢(qián)換成零錢(qián)最小幣值元，一共有多少方式總的不同方式的數(shù)目等于將現(xiàn)金數(shù)換成除第一種幣值之外的所有其他硬幣的不同方式數(shù)據(jù)，加上將現(xiàn)金數(shù)第一種幣值換成所有種類(lèi)的幣值的不同方式，根據(jù)上面的說(shuō)法來(lái)實(shí)現(xiàn)吧實(shí)現(xiàn)中的是中的 原文鏈接: 歡迎 Star 現(xiàn)在有100塊錢(qián)人民幣，將 100 塊錢(qián)換成零錢(qián)（最小幣值 1 元），一共有多少方式？ 總的不同方式的數(shù)目等于： 將現(xiàn)...
閱讀 3789·2021-11-17 09:33
閱讀 2861·2021-09-22 15:12
閱讀 3415·2021-08-12 13:24
閱讀 2520·2019-08-30 11:14
閱讀 1796·2019-08-29 14:09
閱讀 1380·2019-08-26 14:01
閱讀 3144·2019-08-26 13:49
閱讀 1838·2019-08-26 12:16
