C++ dp solution


  • 0
    A
    //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 {
        public:
            int coinChange(vector<int>& coins, int amount) {
                std::vector<int> dp(amount+1, INT_MAX); 
                dp[0]=0;
                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.