Simple C++ DP solution


  • 0
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            static const int INIT=-1;
            vector<int> dp(amount+1,INIT);
            dp[0]=0;
            for (int i=1; i<=amount; ++i) // let i be the sub-amounts up to amount
                for (auto &&coin: coins)
                    if (coin<=i && dp[i-coin]!=INIT)
                        dp[i]=dp[i]==INIT ? 1+dp[i-coin] : min(dp[i],1+dp[i-coin]);
            return dp[amount];
        }
    };
    

Log in to reply
 

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