Leetcode.322.Coin Change

题目

给定一个数组，表示不同面值的硬币。 给定一个数，表示零钱，求出换得零钱最小需要几枚硬币，换不出返回-1。

Input：[1, 2, 5]，11
Output：3
Input：[2]，3
Output：-1

思路

DP。

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

总结

DP千变万化，主要还是理解数学原理，先建立数学模型。