当前位置：首页 > news >正文

【算法-动态规划】零钱兑换 II-力扣 518

news 2025/6/29 8:18:48

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
导航
檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

- - - 1.题目
    - 2.示例
    - 3.二维
    - 4.一维

1.题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

2.示例

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10]
输出：1

3.二维

public class DP_07_ChangeMakingProblemLeetcode518_02 {public int change(int[] coins, int amount) {int[][] dp = new int[coins.length][amount + 1];for (int i = 0; i < coins.length; i++) {dp[i][0] = 1;}for (int j = 1; j < amount + 1; j++) {if (j >= coins[0]) {dp[0][j] = dp[0][j - coins[0]];}}print(dp);for (int i = 1; i < dp.length; i++) {for (int j = 1; j < amount + 1; j++) {if (j >= coins[i]) {dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];}else {dp[i][j] = dp[i - 1][j];}}}print(dp);return dp[coins.length - 1][amount];}public static void main(String[] args) {DP_07_ChangeMakingProblemLeetcode518_02 leetcode = new DP_07_ChangeMakingProblemLeetcode518_02();int count = leetcode.change(new int[]{1, 2, 5}, 5);
//        int count = leetcode.change(new int[]{2}, 3);
//        int count = leetcode.change(new int[]{15, 10, 1}, 21);
//        int count = leetcode.change(new int[]{25, 10, 5, 1}, 41);System.out.println(count);}static void print(int[][] dp) {System.out.println(StringUtil.repeat("-", (18)));for (int[] d : dp) {final Object[] array = Arrays.stream(d).boxed().toArray();System.out.printf((StringUtil.repeat("%2d ", d.length) + "%n"), array);}}
}

4.一维

public class ChangeMakingProblemLeetcode518 {/*面值    0        1        2        3        4        51    1        1        1        1        1        12    1        1        2        2        3        35    1        1        2        2        3        4面值    0        1        2        31        0        0        02    1        0        1        0*/public int change(int[] coins, int amount) {int[] dp = new int[amount + 1];dp[0] = 1;for (int coin : coins) {for (int j = coin; j < amount + 1; j++) {dp[j] = dp[j] + dp[j - coin];}}return dp[amount];}public static void main(String[] args) {ChangeMakingProblemLeetcode518 leetcode = new ChangeMakingProblemLeetcode518();int count = leetcode.change(new int[]{1, 2, 5}, 5);System.out.println(count);}}