322. Coin Change

 動規五部曲分別為:

1. 確定dp數組(dp table)以及下標的含義

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

(from 代碼隨想錄)

 

完全背包：物品有無限個

=> for 物品時由前往後

1/0背包：物品只有一個，選或是不選

=> for 物品時由後往前 (不然會重複選到)

排列：順序重要

=> 先背包再物品 (這樣物品每次都會被考慮到)

組合：順序不重要

=> 先物品再背包

1. 確定dp數組(dp table)以及下標的含義

dp[i] 表示湊成 i 元的最小所需 coin 數

2. 確定遞推公式

dp[i] = max(dp[i], dp[i-coin])

3. dp數組如何初始化

INT_MAX

4. 確定遍歷順序

由左到右

5. 舉例推導dp數組

略

class Solution {

public:

    int coinChange(vector<int>& coins, int amount) {

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

        dp[0] = 0;

        for(auto coin : coins)

        {

            for(int i=coin; i<=amount; i++)

            {

                if(dp[i-coin] == INT_MAX) continue;

                dp[i] = min(dp[i], dp[i-coin] + 1);

            }

        }

        return dp.back() == INT_MAX ? -1 : dp.back();

    }

};