322.coin-change 零钱兑换

问题描述

322.零钱兑换

解题思路

首先，递推关系从最大变成了最小，即dp[j] = min(dp[j], dp[j - coins[i]] + 1)。

同时，要注意对dp数组的初始化问题，为了保证j - coins[i]无法组成时，dp[j]选择的仍是上一次i循环的dp[j]，因此要将dp数组初始化为INT_MAX，同时dp[0] = 0。

要注意INT_MAX + 1 < INT_MAX(在C++中)

代码

#include <limits.h>
#include <vector>
using std::vector;
class Solution {
  private:
    int min(int a, int b) {
        return a < b ? a : b;
    }

  public:
    int coinChange(vector<int> &coins, int amount) {
        if (amount == 0)
            return 0;
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                // 因为可能执行+1的操作， 所以判断dp[j - coins[i]]而不是dp[j]
                if (dp[j - coins[i]] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                // else
                //     dp[j] = dp[j - coins[i]];
            }
        }
        return dp[amount] != INT_MAX ? dp[amount] : -1;
    }
};