C++ dp solution

  • 0
    //let x be the amount, so the dp formula is
    //f(x) =  f(x-coin(i))>=0? 1+ f(x-coin(i)):-1
     class Solution {
            int coinChange(vector<int>& coins, int amount) {
                std::vector<int> dp(amount+1, INT_MAX); 
                std::sort(coins.begin(), coins.end(), std::greater<int>());
                for(int a = 1; a<=amount; a++){
                    for(int i=0; i<coins.size(); i++){
                        if(a>=coins[i] && dp[a-coins[i]]!=-1){
                           dp[a] = std::min(dp[a], (1+dp[a-coins[i]]));
                    if(dp[a]==INT_MAX) dp[a]=-1;
                return dp[amount];

Log in to reply

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