leetcode.322.零钱兑换(动态规划)

零钱兑换

322.零钱兑换

公式

dp[i] = Math.min(dp[i], dp[i - coin] + 1)

代码

class Solution {
public:
  int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1);

    dp[0] = 0;
    for (int n = 1; n <= amount; n++)
    {
      dp[n] = -1;
      for (int i = 0; i < coins.size(); i++)
      {
        if (n - coins[i] >= 0 && dp[n - coins[i]] != -1)
        {
          if (dp[n] == -1)
          {
            dp[n] = dp[n - coins[i]] + 1;
          }
          else if (dp[n] > dp[n - coins[i]] + 1)
          {
            dp[n] = dp[n - coins[i]] + 1;
          }
        }
      }
    }

    return dp[amount];
  }
};