Interview Classic 150 Questions P322 Coin Change

---

Timeline

Timeline

2025-12-12

init

Dynamic Programming

---

Problem:

P322 Coin Change

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

Originally it was a BFS implementation:

#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];
        }
};

Classic knapsack problem DP, taking amount=3 as an example

$$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$$

#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];
        }
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int coinChange(vector<int> &coins, int amount)
        {
                // 1 <= coins.length <= 12
                // 1 <= coins[i] <= 231 - 1
                // 0 <= amount <= 104
                int i, j, n = coins.size();
                vector<int> dp(amount + 1, amount + 1);

                dp[0] = 0;

                for (i = 1; i <= amount; i++) {
                        for (int val : coins) {
                                if (i < val)
                                        continue;
                                dp[i] = std::min(dp[i], dp[i - val] + 1);
                        }
                }

                return (dp[amount] == (amount + 1)) ? -1 : dp[amount];
        }
};