coinChange

硬币找零问题 - 用最少的硬币凑成目标金额。

输入配置

硬币面额 (用逗号分隔)

目标金额

执行过程

步骤 1 / 30

初始化DP数组，dp[0]=0，其余为Infinity

0

0

1

∞

2

∞

3

∞

4

∞

5

∞

6

∞

7

∞

8

∞

9

∞

10

∞

11

∞

速度:慢速正常快速超快

当前计算

可用硬币: 1, 2, 5

算法说明

硬币找零问题：用动态规划计算凑成目标金额所需的最少硬币个数。dp[i]表示凑成金额i所需的最少硬币数。时间复杂度O(amount × n)。

函数签名

// 最少硬币数
function coinChange(coins: number[], amount: number): number

// 组合数
function coinChangeII(coins: number[], amount: number): number

参数

参数名	类型	必填	说明
coins	number[]	是	硬币面额数组
amount	number	是	目标金额

返回值

类型	说明
number	coinChange返回最少硬币数(-1表示无法凑成),coinChangeII返回组合数

工作原理

coinChange (最少硬币数)

动态规划:

1. dp[i]表示凑成金额i所需的最少硬币数
2. 初始化dp[0] = 0,其余为Infinity
3. 状态转移: dp[i] = min(dp[i], dp[i-coin] + 1)
4. 遍历所有金额和所有硬币

时间复杂度: O(amount × n)
空间复杂度: O(amount)

coinChangeII (组合数)

关键: 先遍历硬币,再遍历金额,避免重复计数

时间复杂度: O(amount × n)
空间复杂度: O(amount)