时间轴

2025-12-12

init

题目：

P322 零钱兑换

https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150

原本是BFS写法：

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
27
28
29
30
31
32
33
#include <vector>
#include <queue>
using std::vector;
using std::queue;

class Solution {
public:
        int coinChange(vector<int> &coins, int amount)
        {
                int i, j, n = coins.size();
                int curr;
                vector<int> dp(amount + 1, -1);
                dp[amount] = 0;
                queue<int> que;
                que.push(amount);

                while (!que.empty()) {
                        curr = que.front();
                        que.pop();
                        for (i = 0; i < n; i++) {
                                if (curr - coins[i] >= 0 &&
                                    dp[curr - coins[i]] == -1) {
                                        dp[curr - coins[i]] = dp[curr] + 1;
                                        que.push(curr - coins[i]);
                                        if (curr - coins[i] == 0) {
                                                return dp[0];
                                        }
                                }
                        }
                }
                return dp[0];
        }
};

经典背包问题dp，以amount=3,为例
[
F(3) = \min\big(F(3 - c_1),\; F(3 - c_2),\; F(3 - c_3)\big) + 1
]

[
= \min\big(F(3 - 1),\; F(3 - 2),\; F(3 - 3)\big) + 1
]

[
= \min\big(F(2),\; F(1),\; F(0)\big) + 1
]

[
= \min(1,\; 1,\; 0) + 1
]

[
= 1
]

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
#include <vector>
#include <climits>
using std::vector;

class Solution {
    public:
        int coinChange(vector<int> &coins, int amount)
        {
                int i, j, n = coins.size();

                vector<int> dp(amount + 1, INT_MAX);
                dp[0] = 0;
                for (i = 1; i <= amount; i++) {
                        for (j = 0; j < n; j++) {
                                if (i - coins[j] >= 0 &&
                                    dp[i - coins[j]] != INT_MAX) {
                                        dp[i] = std::min(dp[i - coins[j]] + 1,
                                                         dp[i]);
                                }
                        }
                }

                return dp[amount] == INT_MAX ? -1 : dp[amount];
        }
};