原题链接

题目仅要求出最少硬币数量，无须考虑硬币的组合和排列，所以不用考虑两个 for 循环的内外顺序。

状态定义

dp[i]：凑足总额为 i 所需钱币的最少个数为 dp[i]

状态转移方程

dp[i] = min(dp[j - coins[j]] + 1, dp[i])

理解

不考虑第 j 个硬币时， 硬币数为dp[i]

考虑第 j 个硬币时，硬币数为dp[i - coins[j]] + 1

初始化

凑足总金额为 0 所需钱币的个数是 0，所以dp[0] = 0

下标非 0 元素应该为最大值：Number.MAX_VALUE

constcoinChange=function(coins,amount){constdp=Array(amount+1).fill(Number.MAX_VALUE)dp[0]=0for(leti=1;i<dp.length;i++){for(letj=0;j<coins.length;j++){if(i-coins[j]>=0){dp[i]=Math.min(dp[i],dp[i-coins[j]]+1)}}}returndp[dp.length-1]===Number.MAX_VALUE ?-1 :dp[dp.length-1]}

• 时间复杂度: O(len(coins) * amount)
• 空间复杂度: O(amount)