322. Coin Change

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/coin-change/description/

想法

贪心？

要考虑一些情况，比如：[1, 3, 4], amount = 6:
3 + 3是最优的

DP?

对amount吗？dp[n] = ?
dp[n] = min(dp[n-coins[i]]) + 1

写了一个dp的，但是有测试点没过，没耐心调了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0)
            return 0;
        coins.erase(remove_if(coins.begin(), coins.end(), [amount](int coin){return coin > amount;}), coins.end());
        if (coins.empty())
            return -1;
        vector<int> dp(amount + 1, INT_MAX - 100);
        for (int c : coins) {
            dp[c] = 1;
        }
        for (int i = *std::max_element(coins.begin(), coins.end()) + 1; i <= amount; i++) {
            int min = INT_MAX - 100 + 1;
            for (int j = 0; j < coins.size(); j++) {
                if (dp[i - coins[j]] + 1 < min) {
                    min = dp[i - coins[j]] + 1;
                }
            }
            dp[i] = min;
        }
        if (dp[amount] == INT_MAX - 100 + 1)
            return -1;
        return dp[amount];
    }
};

看了discussion，思路是一样的，就是一点也不清晰！！！

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

想法

为什么自己这么菜呢？？？

思路不清晰！！！
算法不熟练！！！

多练哇！！！
太菜啦！！！
菜到自己都看不下去啦！！！