322. Coin Change - cocoder39/coco39_LC GitHub Wiki

322. Coin Change

consider DP when facing "minimum" problem. It works like picking out some points from the sequence first, then pick a bunch of points that are reachable from already reachable points.

dp[i] is the number of coins needed to make up amount, use dp[i + coin] = min(dp[i + coin], dp[i] + 1) to update dp[i + coin]. corner cases include amount = 0, coin is a very large number

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (auto coin : coins) {
            if (coin > amount) {
                continue;
            }
            dp[coin] = 1;
        }
        
        for (int i = 1; i <= amount; i++) {
            if (dp[i] == -1) {
                continue;
            }
            for (auto coin : coins) {
                if (i + coin > amount) {
                    continue;
                }
                dp[i + coin] = dp[i + coin] == -1 ? dp[i] + 1 : min(dp[i + coin], dp[i] + 1);
            }
        }
        return dp[amount];
    }

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) {
            if (coins[i] <= amount) {
                dp[coins[i]] = 1; 
            }
        }
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i > coins[j] && dp[i - coins[j]] != -1) {
                    if (dp[i] == -1) {
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                    else {
                        dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                    }
                }
            }
        }
        return dp[amount];
    }

second round

int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end());
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (int i = 0; i < amount; i++) { // O(amount * coins.size())
            if (dp[i] != -1) {
                for (auto coin : coins) {
                    if (i > amount - coin) { // i + coin > amout may cause overflow
                        break;
                    }
                    if (dp[i + coin] == -1 || dp[i + coin] > dp[i] + 1) {
                        dp[i + coin] = dp[i] + 1;
                    }
                }
            }
        }
        return dp[amount];
    }
⚠️ **GitHub.com Fallback** ⚠️