# 322.零钱兑换

## 问题描述
[322.零钱兑换](https://leetcode.cn/problems/coin-change/)

## 解题思路
首先，递推关系从最大变成了最小，即`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++中)

## 代码
```cpp
#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;
    }
};
```