[Day 5] Leetcode 322. Coin Change (C++)

前言

天啊今天整个非常赶，23:00到家打开发现今天是hard的题目(446. Arithmetic Slices II - Subsequence)，匆忙看了一下，感觉来不急消化後写出来，先来拿个以前做过的经典题目应急~
我们来看看这题吧！322. Coin Change，是属於top 100 liked的一题，也是DP的经典题目啊！

想法

这题目乍看之下你会有什麽想法呢？如果是台湾的情况，有1块钱,5块钱,10块钱,50块钱，你应该觉得这有够直觉不用算，最少的情形一定是先/50+余数/10+余数/5+余数/1，就好啦！有够直觉，而且必定正确！
但这题可不能这样算！为什麽呢？如果今天的钱币面额是2,7,10，我随便乱举，那如果现在要凑18块钱，你照上面的想法直接算18/10，先用10块，剩下8块/7，再用一个7块，挖，尴尬了，现在剩1块，但我面额最小只有2块，凑不出来！
但答案并不是凑不出来，因为我明明就可以用1个10块跟4个2块解决啊！
p.s.你也可以想想看为什麽台湾的1,5,10情形一定可以直接用上述那种简单暴力的做法算出来XD
为什麽说它是经典的题目呢？试想昨天提到的DP概念，我们是不是可以往回推前一个状态呢？现在我们需要18块，我们可以知道它可以凑到16块再加一个2元硬币，或是凑到13块再加一个5元硬币，或是凑到8块再加一个10元硬币，然後要求最少的硬币的情况下，我们是不是就找到凑到16块/13块/8块的情形中，最少的那种，再+1就会是凑到18块的答案了呢？这样是不是有想法了呢？
那我们就又可以出动我们的纪录阵列/矩阵啦！我们现在要凑到amount元，现在面额有coins面额的情形，我们可以建立一个amount+1那麽大的阵列来记录：(为什麽要+1?因为我们需要0元的数量比较好算一点。继续看就知道了)
第二个amount+1是我们给这个阵列的初始值，给的原因是要确保一个肯定比正确答案来得大的数值(题目说面额最小的可能是1元，所以绝对不会出现100块要101个硬币才能凑出来的情形~)

vector<int> dp(amount+1,amount+1);

接下来怎麽做呢？我们就开始从前面往後推吧！针对现在的每一个暂时的amount，我们要去求它最少的硬币数量多少，那就是去算该amount-各硬币面额的情况下的数量，然後再+1；那如果amount-下去已经低於该面额就不用算了(就是 现在我只差3块钱，但目前这个面额是5，那就不用考虑啦QQ)，那以下就是照这个逻辑的完整程序了：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // set a value that is guaranteed to bigger than the possible answer
        // the smallest possible coin value is 1, so there may not be anwer that has to have amount+1 coins to build up the amount
        int ub = amount + 1;
        // record the smallest coins to get the each amount
        vector<int> dp(amount + 1, ub);
        // sort the coins so we could consider less cases
        sort(coins.begin(), coins.end());
        // start from 0 coins
        dp[0] = 0;
        // compute each amount coin numbers from 0
        for (int i = 1; i <= amount; ++i) {
            // consider the last coin as each coins value
            for (int j = 0; j < coins.size(); ++j) {
                // ensure dp[i - coins[j]] is valid
                if (i-coins[j]<0) {
                    continue;
                }
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        
        return dp[amount]!=ub?dp[amount]:-1;
    }
};

结语

leetcode的每日挑战截止时间其实是台湾下午3点，以後还是前一天先写好题目隔天拿前一天的题目发文好了Orz