在昨天的文章關(guān)于背包問題的一點(diǎn)發(fā)散之后，有小伙伴說感覺跟LeetCode上一道題零錢兌換很像，但是又好像有點(diǎn)不一樣，簡單的暴力遞歸跟緩存優(yōu)化都能做出來，就是自下而上的方法不怎么有思路。我看了下，其實(shí)這道題跟我們昨天的題目有異曲同工之處，可以說極度相似，今天我們就來分析分析這道題。

題目我再貼出來：給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

我們來看兩個(gè)例子：
輸入: coins = [1, 2, 5], amount = 11 輸出: 3
輸入: coins = [2], amount = 3 輸出: -1

每次遇到這樣的問題我們總是本能地用暴力遞歸來做，沒有問題，先實(shí)現(xiàn)，后期優(yōu)化，跟隨自己的想法來。暴力遞歸無需過多分析了，無非是遞歸地做選擇，選擇硬幣，然后選擇硬幣最少的那個(gè)方案。

咱們直接上遞歸代碼，咱們主要思考分析工作在后期的算法優(yōu)化上。

public int countChange(int[] denominations, int total) {
        int result = this.countChangeRecursive(denominations, total, 0);
        return (result == Integer.MAX_VALUE ? -1 : result);
    }

    private int countChangeRecursive(int[] denominations, int total, int currentIndex) {
        if (total == 0)
            return 0;

        if (denominations.length == 0 || currentIndex >= denominations.length)
            return Integer.MAX_VALUE;

        // 不停地做選擇，只要當(dāng)前面值比剩余數(shù)目小，我們都可以選擇這個(gè)硬幣
        int count1 = Integer.MAX_VALUE;
        if (denominations[currentIndex] <= total) {
            int res = countChangeRecursive(denominations, total - denominations[currentIndex], currentIndex);
            if (res != Integer.MAX_VALUE) {
                count1 = res + 1;
            }
        }

        // 直接跳過當(dāng)前面值，進(jìn)行下一次選擇
        int count2 = countChangeRecursive(denominations, total, currentIndex + 1);

        return Math.min(count1, count2);
    }

這邊由于是選擇可以的最小數(shù)目，所以我們把邊界條件設(shè)置成Integer的最大值。這個(gè)時(shí)間復(fù)雜度也很容易看出來了，是O(2^(T+C))。T是需要換零的總數(shù)額，C是硬幣種類數(shù)量。

寫到這里我們就可以做第一步優(yōu)化了，這是我們第四次討論這樣的題目了，基本上可以判斷通過緩存可以把算法復(fù)雜度進(jìn)一步優(yōu)化。每次做選擇的時(shí)候，變化的只有剩余需要換零數(shù)額跟當(dāng)前硬幣的索引，所以我們可以用一個(gè)二維數(shù)組來存儲(chǔ)已經(jīng)算得的結(jié)果。

public int countChange(int[] denominations, int total) {
        Integer[][] dp = new Integer[denominations.length][total + 1];
        int result = this.countChangeRecursive(dp, denominations, total, 0);
        return (result == Integer.MAX_VALUE ? -1 : result);
    }

    private int countChangeRecursive(Integer[][] dp, int[] denominations, int total, int currentIndex) {
        if (total == 0)
            return 0;

        if(denominations.length == 0 || currentIndex >= denominations.length)
            return Integer.MAX_VALUE;

        // 如果之前已經(jīng)遇到過同樣場(chǎng)景，直接返回結(jié)果
        if(dp[currentIndex][total] == null) {
            // 只要當(dāng)前硬幣面額比剩余需換零數(shù)目小，我們就可以考慮用它來換零
            int count1 = Integer.MAX_VALUE;
            if( denominations[currentIndex] <= total ) {
                int res = countChangeRecursive(dp, denominations, total - denominations[currentIndex], currentIndex);
                if(res != Integer.MAX_VALUE){
                    count1 = res + 1;
                }
            }

            // 直接跳過當(dāng)前面額，去選擇其他面額
            int count2 = countChangeRecursive(dp, denominations, total, currentIndex + 1);
            dp[currentIndex][total] = Math.min(count1, count2);
        }
        return dp[currentIndex][total];
    }

相信這兩步對(duì)大家都沒什么難度，大家可以很輕松地做到這一步。我們直接來思考一下自下而上的方式，我們?cè)撛趺醋觥?/p>

本質(zhì)上，遇到任何面值的硬幣，對(duì)于任何需要換零的數(shù)目，我們都想用最少的硬幣來完成。那么對(duì)于所有可能的total ‘t’ (0<= t <= 總的換零數(shù)目) 和所有可能的硬幣index (0 <= index < 硬幣種類數(shù)目)，我們有兩種選擇：

1. 跳過當(dāng)前面額的硬幣，那么此時(shí)我們可以得到的最小硬幣數(shù)就是dp[index-1][t]。
2. 當(dāng)前硬幣面額小于需要換零額度時(shí)，我們就用它來換零，在這種情況下，我們就需要拿到能換到剩余數(shù)額的最小硬幣數(shù)。那此時(shí)的最小硬幣數(shù)就是dp[index][t-denominations[index]] + 1。

最終，我們的最小硬幣數(shù)一定是這兩種選擇中最小的那一個(gè)。dp[index][t] = min(dp[index-1][t], dp[index][t-denominations[index] + 1)?？赡芄膺@么說有點(diǎn)抽象，我們來具體點(diǎn)。

假使面值: [1, 2, 3] 換零總額: 7。

零錢兌換

原諒我不會(huì)畫表格，當(dāng)我們只有面值為一的硬幣時(shí)，我們要還多少錢就要多少個(gè)硬幣。當(dāng)我們有面值為1，2兩種的硬幣時(shí)，當(dāng)我們對(duì)5進(jìn)行兌換時(shí)，不選擇2這個(gè)面值的話，dp[0][5]是5，也就是我們需要5個(gè)面值為1的硬幣，而dp[1][3]是是2，那這種情況兌換硬幣就只要3個(gè)。最終兌換5所需最少硬幣數(shù)就是3.

好了，思路都解釋清楚了，剩下來的就是代碼實(shí)現(xiàn)了。

public int countChange(int[] denominations, int total)
    {
        int n = denominations.length;
        int[][] dp = new int[n][total + 1];

        for(int i=0; i < n; i++)
            for(int j=0; j <= total; j++)
                dp[i][j] = Integer.MAX_VALUE;

        // 換零金額是0的時(shí)候需要的硬幣當(dāng)然為0
        for(int i=0; i < n; i++)
            dp[i][0] = 0;

        for(int i=0; i < n; i++) {
            for(int t=1; t <= total; t++) {
                if(i > 0)
                    dp[i][t] = dp[i-1][t]; //不選擇當(dāng)前硬幣
                if(t >= denominations[i]) {
                    if(dp[i][t-denominations[i]] != Integer.MAX_VALUE)
                        dp[i][t] = Math.min(dp[i][t], dp[i][t-denominations[i]]+1); // 西安則當(dāng)前硬幣
                }
            }
        }

        // 最佳答案照例出現(xiàn)在最角落里
        return (dp[n-1][total] == Integer.MAX_VALUE ? -1 : dp[n-1][total]);
    }

哎，好了，這時(shí)候的復(fù)雜度就只有O(T*C)了，這么一看，我們這道題其實(shí)還是很簡單的，LeetCode很多題目的題面本身都已經(jīng)暗示我們要用什么方法來解題了，只要努力把它轉(zhuǎn)化成我們熟悉的題目，往我們會(huì)的思路上靠就可以了。