C++ recursive dp solution


  • 0
    A
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            vector<int> dp(amount + 1, -1);
            sort(coins.begin(), coins.end());
            
            if (amount == 0) {
                return 0;
            }
            
            if (coins[0] > amount) {
                return -1;
            }
            
            for(int c: coins) {
                if (c <= amount) {
                    dp[c] = 1;
                }
            }
            
            int mini = coinsMin(coins, dp, amount);
            return mini;
        }
        
        int coinsMin(vector<int> &coins, vector<int> &dp, int amount) {
            if (amount < 0) {
                return -1;
            } else if (amount == 0) {
                return 0;
            } else if (dp[amount] == -2) {
                return -1;
            } else if (dp[amount] != -1) {
                return dp[amount];
            } else {
                if (coins[0] > amount) {
                    return -1;
                }
                int mini = INT_MAX;
                int temp;
                for(int c: coins) {
                    temp = coinsMin(coins, dp, amount - c);
                    
                    if (temp == -1)
                        continue;
                        
                    mini = min(mini, 1 + temp);
                } 
                
                if (mini == INT_MAX) {
                    dp[amount] = -2;
                    return -1;
                }
                dp[amount] = mini;
                return mini;
            }
        }
    };
    

Log in to reply
 

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