LeetCode 322: Coin Change (1D Dynamic Programming)

2026-03-16 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 322DPComplete Knapsack

Today we solve LeetCode 322 - Coin Change.

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

LeetCode 322 coin change DP transition diagram

English

Problem Summary

Given coin denominations coins and an integer amount, return the minimum number of coins needed to make up amount. If impossible, return -1.

Key Insight

This is a minimum-step complete knapsack: each coin can be used unlimited times, and we want the smallest count. Let dp[x] be the minimum coins needed to make sum x.

Brute Force and Limitations

DFS tries all combinations and can explode exponentially. Even with memoization, you still need careful state design and transitions. Bottom-up DP is cleaner and predictable.

Optimal Algorithm Steps

1) Initialize dp[0] = 0, others as INF (e.g. amount + 1).
2) For every target sum x from 1 to amount:
3) Try each coin c. If x - c >= 0, transition:
dp[x] = min(dp[x], dp[x-c] + 1).
4) Final answer is dp[amount], unless it is still INF.

Complexity Analysis

Time: O(amount * len(coins)).
Space: O(amount).

Common Pitfalls

- Forgetting impossible case and returning INF directly.
- Initializing INF too large and causing overflow in dp[x-c] + 1.
- Mixing 0/1 knapsack loop order with complete knapsack understanding.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int inf = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, inf);
        dp[0] = 0;

        for (int x = 1; x <= amount; x++) {
            for (int c : coins) {
                if (x - c >= 0) {
                    dp[x] = Math.min(dp[x], dp[x - c] + 1);
                }
            }
        }

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

func coinChange(coins []int, amount int) int {
    inf := amount + 1
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = inf
    }

    for x := 1; x <= amount; x++ {
        for _, c := range coins {
            if x-c >= 0 && dp[x-c]+1 < dp[x] {
                dp[x] = dp[x-c] + 1
            }
        }
    }

    if dp[amount] == inf {
        return -1
    }
    return dp[amount]
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int inf = amount + 1;
        vector<int> dp(amount + 1, inf);
        dp[0] = 0;

        for (int x = 1; x <= amount; ++x) {
            for (int c : coins) {
                if (x - c >= 0) {
                    dp[x] = min(dp[x], dp[x - c] + 1);
                }
            }
        }

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

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        inf = amount + 1
        dp = [inf] * (amount + 1)
        dp[0] = 0

        for x in range(1, amount + 1):
            for c in coins:
                if x - c >= 0:
                    dp[x] = min(dp[x], dp[x - c] + 1)

        return -1 if dp[amount] == inf else dp[amount]

var coinChange = function(coins, amount) {
  const inf = amount + 1;
  const dp = new Array(amount + 1).fill(inf);
  dp[0] = 0;

  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (x - c >= 0) {
        dp[x] = Math.min(dp[x], dp[x - c] + 1);
      }
    }
  }

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

中文

题目概述

给定硬币面额数组 coins 和金额 amount，求凑出该金额所需的最少硬币数；若无法凑出，返回 -1。

核心思路

这是典型的完全背包最小值问题。定义 dp[x] 为凑成金额 x 的最少硬币数，通过更小金额状态转移得到当前最优解。

暴力解法与不足

回溯会枚举大量重复组合，复杂度指数级。即使用记忆化，思路仍较绕；自底向上的一维 DP 更稳定、实现更简洁。

最优算法步骤

1）初始化 dp[0] = 0，其余设为 INF（如 amount + 1）。
2）遍历目标金额 x = 1..amount。
3）枚举每个硬币 c，若 x-c >= 0，执行：
dp[x] = min(dp[x], dp[x-c] + 1)。
4）若最终 dp[amount] 仍为 INF，返回 -1，否则返回该值。

复杂度分析

时间复杂度：O(amount * n)（n = coins.length）。
空间复杂度：O(amount)。

常见陷阱

- 忘记处理不可达金额，直接输出 INF。
- INF 选择不当导致 +1 溢出。
- 把状态转移顺序和 0/1 背包混淆，导致理解偏差。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int inf = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, inf);
        dp[0] = 0;

        for (int x = 1; x <= amount; x++) {
            for (int c : coins) {
                if (x - c >= 0) {
                    dp[x] = Math.min(dp[x], dp[x - c] + 1);
                }
            }
        }

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

func coinChange(coins []int, amount int) int {
    inf := amount + 1
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = inf
    }

    for x := 1; x <= amount; x++ {
        for _, c := range coins {
            if x-c >= 0 && dp[x-c]+1 < dp[x] {
                dp[x] = dp[x-c] + 1
            }
        }
    }

    if dp[amount] == inf {
        return -1
    }
    return dp[amount]
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int inf = amount + 1;
        vector<int> dp(amount + 1, inf);
        dp[0] = 0;

        for (int x = 1; x <= amount; ++x) {
            for (int c : coins) {
                if (x - c >= 0) {
                    dp[x] = min(dp[x], dp[x - c] + 1);
                }
            }
        }

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

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        inf = amount + 1
        dp = [inf] * (amount + 1)
        dp[0] = 0

        for x in range(1, amount + 1):
            for c in coins:
                if x - c >= 0:
                    dp[x] = min(dp[x], dp[x - c] + 1)

        return -1 if dp[amount] == inf else dp[amount]

var coinChange = function(coins, amount) {
  const inf = amount + 1;
  const dp = new Array(amount + 1).fill(inf);
  dp[0] = 0;

  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (x - c >= 0) {
        dp[x] = Math.min(dp[x], dp[x - c] + 1);
      }
    }
  }

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