Sharing my 132ms C++ solution


  • 8
    T
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            vector<int> DP(amount+1, INT_MAX-1);
            // DP[i]: the result when amount = i;
            int n = coins.size(), i, j;
            DP[0] = 0; // no coins when amount = 0
            for(i=1; i<=amount; i++)
            {
                for(j=0; j<n; j++)
                {
                    if(i-coins[j]>=0)
                        DP[i] = min(DP[i], DP[i-coins[j]]+1);
                }
            }
            
            if(DP[amount] == INT_MAX-1)
                return -1;
            else
                return DP[amount];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.