518. Coin Change 2

Posted on | Edited on | In , |

518. Coin change 2

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

本来超时的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        std::sort(coins.begin(), coins.end(), std::greater<int>());
        return changeRem(amount, coins);
    }
    int changeRem(int amount, vector<int>& coins) {
        if (coins.empty()) {
            if (amount == 0)
                return 1;
            else
                return 0;            
        }
        int res = 0;
        std::vector<int> remain(coins.begin() + 1, coins.end());
        for (size_t i = 0; i <= amount / coins[0]; i++) {
            res += changeRem(amount - i * coins[0], remain);
        }
        return res;
    }
};

暴力遍历的方式，轻松就超时了。

关键思想： DP
DP是容易想到的，但是本来自己想的DP老是纠结在如何通过n-1的得到n的，但实际上这的确有点难操作。

更好的想法是，如果有一个k面值的coin，那么，n处的可能数就多了n-k个
另外，还要搞清楚的一点是，dp[0] == 1，这是dp的初始条件！

AC的解法，3ms

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