Dp O(amount*coins.size()) cpp solution


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

  • -2
    D

    but if amount = pow(2,32)-1,your code is Obviously wrong


  • 0
    E

    If amount is so large, we would have memory limit exceeded error anyway :)


Log in to reply
 

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