C++ Solution using DP with O(n*amount) Time complexity and O(amount) Space complexity


  • 2
    Y
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int ans;
            if(!coins.size() && amount)
               return -1;
            int INF = amount + 1;
            vector<int> dp(amount + 1, INF);
            dp[0] = 0;
            for(int i = 0; i < coins.size(); ++ i){
                for(int j = coins[i]; j <= amount; ++ j){
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
            
            return dp[amount] == INF?-1:dp[amount];
        }
    };

Log in to reply
 

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