518. 零钱兑换 II（JavaScript）

前端-pww

于 2022-03-01 15:51:05 发布

阅读量198

点赞数 1

分类专栏：力扣算法题文章标签： javascript 动态规划算法 leetcode 前端

本文链接：https://blog.csdn.net/csD_Dscnnnnnnn/article/details/123208013

版权

力扣算法题专栏收录该内容

170 篇文章

订阅专栏

这篇博客介绍了一个使用动态规划求解找零问题的算法。通过遍历所有硬币类型并更新背包状态，计算出凑满指定金额的组合数。算法适用于每个硬币可以无限次使用的情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

 //输出硬币的组合数
 //每个元素可多次选择，完全背包
 //凑满金额，装满背包dp[j]+=dp[j-w[i]]
var change = function(amount, coins) {
    //dp的长度取决于背包的容量
    let dp=new Array(amount+1).fill(0)
    //累加记得初始化第一个为1
    dp[0]=1
    let len=coins.length

    for(let i=0;i<len;i++){  //遍历下标（物品）
        for(let j=coins[i];j<=amount;j++){   //遍历背包容量
            dp[j]+=dp[j-coins[i]]
        }
    }
    return dp[amount]
};