Week9

Dynamic Programming

question source: Coin Change

question description

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:

Input: coins = [1, 2, 5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3

Output: -1

Note:

You may assume that you have an infinite number of each kind of coin.

這是一道标簽為動态規劃的題。這兩周學習了動态規劃的内容，以及相關經典問題的讨論。說實話，這部分内容比較難想，但一旦想出來，實作就比較簡單。老師上課的時候老說，其實不難，照着書本上和老師的分析來想，自然是不難，但是要自己想呢，還是要多做題才有感覺。現在來看這道題，是說給你一個數目，把它分成若幹個硬币的組合，求這個組合的最小數目，如果不能拆分，就傳回-1。

解決方法

這實際上是背包問題的變種，背包問題在上課時有讨論過。用動态規劃的思想來解決問題。動态規劃是一種非常強大的計算模式，其解決問題的方式是首先定義它的一組子問題，然後按照由小到大，以小問題的解答支援大問題求解的模式，依次解決所有子問題，并最終得到原問題（最大的子問題）的求解。

我們要用一種途徑來縮小原來的問題，這裡自然想到用較小的金額。

定義 k ( m ) = 金 額 為 m 分 解 的 最 小 硬 币 個 數 。 k(m) = 金額為m分解的最小硬币個數。 k(m)=金額為m分解的最小硬币個數。

那麼對于某些i，就存在 K ( m ) = k ( m − m i ) K(m) = k(m - m_i) K(m)=k(m−mi​)

這個i，必須要使得k(m)最小。因為我們不知道究竟是哪個i，是以要嘗試所有的可能。是以，

K ( m ) = min ⁡ i : m i &lt; = m { k ( m − m i ) + 1 } K(m) = \min_{i: m_i &lt;= m} \lbrace k(m - m_i) + 1 \rbrace K(m)=i:mi​<=mmin​{k(m−mi​)+1}

然後就要定義最小的子問題了。K(0)肯定是0咯。先預設k（m）為-1，表示不能拆分，然後看 k ( m − m i ) k(m - m_i) k(m−mi​) 是不是也是-1，如果對于全部的i都是，則說明k（m）不能拆分，設為-1，否則就更新為最小的。

然後就從左到右填寫一個長度為amount + 1的一維表格，總的計算時間為O(n * amount)。

實作代碼如下

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int num[amount + 1];
        num[0] = 0;
        for(int i = 1; i <= amount; i++){
            int minum = -1;
            for(int j = 0; j < coins.size(); j++){
                int kid = i - coins[j];
                if(kid >= 0){
                    if(num[kid] != -1){
                        if(minum == -1){
                            minum = num[kid] + 1;
                        }else{
                            minum = std::min(minum, num[kid] + 1);
                        }
                    }
                }
            }
            num[i] = minum;
        }
        return num[amount];
    }
};
           

運作的效果還行。動态規劃真的很簡單高效，隻要有一個公式定義原問題與子問題的關系，就很容易實作，很好用。問題就是有的問題沒這麼容易想。