Description Link to heading

322.coin-change

Solution Link to heading

The recursive relationship change from max to min: dp[j] = min(dp[j], dp[j - coins[i]] + 1).

We need pay attention to issue about initializing dp array. To ensure that if j - coins[i] can’t be come up with, dp[j] is still dp[j] in last loop, we should initialize dp as INT_MAX, and dp[0] = 0.

Attention: INT_MAX + 1 < INT_MAX(in C++)

Code Link to heading 

#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++) {
                // since that we may add dp[j - coins[i]] + 1,
                // we should ensure that dp[j - coins[i]] is not INT_MAX
                if (dp[j - coins[i]] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] != INT_MAX ? dp[amount] : -1;
    }
};