Leetcode #518 - Coin Change 2

這是 June LeetCoding Challenge 6/7 的題目。

問題

全文：https://leetcode.com/problems/coin-change-2/

給你不同面額的硬幣與錢的總額，計算有多少種組合的硬幣可以湊出那筆錢的金額。可以假設每種硬幣都有無限多個。

手算

如果不知道怎麽解的話，可以試著代數字看看，下面用範例一的數字說明，也就是：

用 1 元、2 元及 5 元硬幣湊成 5 元，有幾種湊法？

我們可以從面額大的硬幣開始選，畫出樹狀圖：

然後把所有情形列成表格：

5 元	2 元	1 元
0	0	5
0	1	3
0	2	1
1	0	0

可以發現 5 元一共有 4 種湊法。

DFS

在上面的解法中，我們做了：

把硬幣種類由大排到小
列出第一種硬幣（5 元）的可能數量（0 個或 1 個）
對第一種硬幣每個可能的數量，都找出第二種硬幣（2 元）的可能數量
（0 個 5 元：0-2 個 2 元；1 個 5 元：0 個 2 元）
對於上面列出的硬幣組合，找出對應的第三種硬幣（1 元）數量

我們可以把這種方法寫成程式，這個程式相當於對上面的樹狀圖進行遍歷。

class Solution {
public:
    int dfs(vector<int>& coins, int coinType, int targetAmount, int currentAmount) {
        int ans = 0;
        for(; currentAmount <= targetAmount && coinType < coins.size(); currentAmount += coins[coinType]) {
            if(currentAmount < targetAmount) {
                ans += dfs(coins, coinType + 1, targetAmount, currentAmount);
            } else if(currentAmount == targetAmount) {
                ans++;
            }
        }
        return ans;
    }

    int change(int amount, vector<int>& coins) {
        sort(coins.begin(), coins.end(), greater<int>());
        return dfs(coins, 0, amount, 0);
    }
};

如果拿上面的程式進行檢測，會超過時間。不過是有用 DFS 通過的解答，像是討論中的這篇。

生成函數

先看看生成函數的定義，對一個數列 $\lang a_n \rang$ ，它的生成函數是

G(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots=\displaystyle\sum_{k=0}^\infty a_kx^k

回到一開始的問題：

用 1 元、2 元及 5 元硬幣湊成 5 元，有幾種湊法？

Rosen 的離散數學裡有這個例題。如果數列 $\lang a_n \rang$ 的第 k 項代表湊成 k 元的方法，我們可以寫出它的生成函數：

(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^5+x^{10}+\dots)

乘積的第一項代表只使用 1 元硬幣的湊法，第二項代表只使用 2 元硬幣的湊法，而第三項代表只使用 5 元硬幣的湊法。

把它乘開，

1+x+2x^2+2x^3+3x^4+4x^5+\dots

$x^5$ 的係數是 4，所以湊成 5 元的方法數是 4 種。

我們可以用這樣的方法寫出程式：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> ans(amount + 1, 0);
        ans[0] = 1;

        for(auto coin : coins) {
            vector<int> gf(amount + 1, 0);
            vector<int> tmp(amount + 1, 0);
            for(int i = 0; i <= amount; i += coin)
                gf[i] = 1;
            for(int i = 0; i <= amount; ++i) {
                int sum = 0;
                for(int j = 0; j <= i; ++j)
                    sum += ans[j] * gf[i - j];
                tmp[i] = sum;
            }
            ans = tmp;
        }

        return ans[amount];
    }
};

這個程式會 TLE。不過因為這邊多項式的係數只會是 0 或 1，所以可以用這個特性簡化：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> ans(amount + 1, 0);
        ans[0] = 1;

        for(auto coin : coins) {
            vector<int> tmp(amount + 1, 0);
            for(int i = 0; i <= amount; ++i) {
                int sum = 0;
                for(int j = 0; j <= i; j += coin)
                    sum += ans[i - j];
                tmp[i] = sum;
            }
            ans = tmp;
        }

        return ans[amount];
    }
};

這樣就可以過了，然而這個方法相較於下面的解法，時間還是差很多。

（這則討論的解法也用到了生成函數。）

動態規劃

現在我們用不同的觀點再算一次 0-5 元的湊法。

如果先計算只有 1 元硬幣的情況：

金額	0 元	1 元	2 元	3 元	4 元	5 元
湊法	1	1	1	1	1	1

因為每個金額都能、而且只能用 1 元湊出來，所以每個金額都只有 1 種湊法。

然後把 2 元硬幣考慮進去，計算有 1 元與 2 元硬幣的情況：

金額	0 元	1 元	2 元	3 元	4 元	5 元
湊法	1	1	2	2	3	3

這邊，2 元除了只有 1 元硬幣的 1 種湊法以外，還有 1 個 2 元硬幣的 1 種湊法，所以是 2 種。

3 元除了只有 1 元硬幣的 1 種湊法以外，還可以拿 1 元加上 1 個 2 元硬幣。1 元有 1 種湊法，所以 3 元有 1 + 1 = 2 種。

同理，4 元除了只有 1 元硬幣的 1 種湊法以外，還可以拿 2 元加上 1 個 2 元硬幣。2 元有 2 種湊法，所以 4 元有 1 + 2 = 3 種。

再加入 5 元硬幣，可以算出：

金額	0 元	1 元	2 元	3 元	4 元	5 元
湊法	1	1	2	2	3	4

因為 5 元除了前面的 3 種湊法，還可以只用 1 個 5 元硬幣湊出來，所以一共是 4 種湊法。

算到這邊，可以看出一個平常很難想出來的式子：

前 i 種硬幣湊出 x 元的方法 = 前 i - 1 種硬幣湊出 x 元的方法 + 前 i 種硬幣湊出 x - c 元的方法

其中 c 為第 i 種硬幣的面額。

可以把上面的想法寫成遞迴的數學式：

設第 $i$ 種硬幣面額是 $c_i$ ，前 $i$ 種硬幣湊出 $j$ 元的方法是 $m[i, j]$ ，

m[i, j] = \begin{cases} 1 &\text{if } i=0\text{ and } j=0 \\ 0 &\text{if } i=0\text{ and } j>0 \\ m[i-1, j] &\text{if } i>1\text{ and } j < c_i \\ m[i-1, j] + m[i, j-c_i] &\text{if } i>1\text{ and } j \geq c_i \end{cases}

前兩行是初始值， $i = 0$ 代表沒有任何硬幣。在沒有任何硬幣的時候是可以湊出 0 元的，因為只要不選硬幣就好（反正也沒有硬幣），這樣就算是一種湊法。但是沒有硬幣的時候湊不出其他金額，所以湊法有 0 種。

第三行因為 $m[i, j-c_i]$ 不存在（ $j-c_i<0$ ），所以不用加上這一項。

第四行就是上面文字的數學符號版本。

把上面的式子寫成程式就變成：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> m(coins.size() + 1, vector<int>(amount + 1, 0));
        m[0][0] = 1;
        for(int i = 1; i <= coins.size(); ++i)
            for(int j = 0; j <= amount; ++j) {
                if(j < coins[i - 1])
                    m[i][j] = m[i - 1][j];
                else
                    m[i][j] = m[i - 1][j] + m[i][j - coins[i - 1]];
            }
        return m[coins.size()][amount];
    }
};

在上面的程式中，我們做了一個二維 vector m，照上面的式子計算，最後得到答案 m[coins.size()][amount]。

仔細看程式可以發現對 m[i] 的所有元素，m[i][j] 的值跟上一行的關係只在於 m[i - 1][j]。在這一列算到 j 之前，m[i][j] 都不會被動到，這代表我們可以安心的只用一列儲存這個 vector。

把上面的程式簡化後可以得到最後的答案：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> m(amount + 1, 0);
        m[0] = 1;
        for(int i = 1; i <= coins.size(); ++i)
            for(int j = coins[i - 1]; j <= amount; ++j) {
                m[j] += m[j - coins[i - 1]];
            }
        return m[amount];
    }
};

m[i][j] = m[i - 1][j]; 這一行在 m 改成一維 vector 之後就沒用了，把它去掉。再把剩下的 j >= coins[i - 1] 這個條件跟 for 迴圈合併，讓 j 從 coins[i - 1] 開始就能確保上述條件永遠為真。