leetcode322. Coin Change

kohoh_ 發(fā)布于2019-08-15 14:41 / 1040人閱讀

摘要：傳入的參數(shù)為手上有的紙幣的面額以及希望兌換的面額。這里假設(shè)紙幣的數(shù)量是無窮的。這題本質(zhì)上考察的是動態(tài)規(guī)劃思想。這里有兩種動態(tài)規(guī)劃的方法，分別從遞歸和非遞歸的角度解決這個問題。具體的情況還是要看數(shù)據(jù)的分布情況來確定選擇哪種方法。

題目要求

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.

這里模擬實現(xiàn)了一個換錢算法。傳入的參數(shù)為手上有的紙幣的面額以及希望兌換的面額。這里假設(shè)紙幣的數(shù)量是無窮的。

這題本質(zhì)上考察的是動態(tài)規(guī)劃思想。這里有兩種動態(tài)規(guī)劃的方法，分別從遞歸和非遞歸的角度解決這個問題。具體的情況還是要看數(shù)據(jù)的分布情況來確定選擇哪種方法。

非遞歸

這里我們新建一個臨時數(shù)組result，下標(biāo)i上的值來存儲用當(dāng)前手上的紙幣兌換面額i時所需要的最少的紙幣數(shù)量。這樣，假設(shè)有一個紙幣數(shù)組[coin[0], coint[1], ..., coin[k]]，我們需要計算兌換面額i所需要的最小數(shù)量的紙幣，那么只需要比較[result[i-coin[0]], result[i-coin[1]], result[i-coin[2]] ... , result[i-coint[k]]]即可。這里需要考慮一些越界情況比如手上紙幣面額比需兌換面額大。還有可能result[i-coin[t]]是無法兌換的。

    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ù)組作為一個緩存來減少重復(fù)計算的損耗。其實這里的代碼還是可以繼續(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

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~