【LeetCode】零钱兑换 IIJava 题解

关注

发布于: 2021 年 06 月 10 日

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

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

复制代码

思路分析

通读题目，题干容易理解，首先想到的是枚举所有 coins 的子集，在求出与 amount 相等的组合数。这种思路的弊端是没有考虑到硬币的个数可以是无限，思路错误。
求组合数，比较常见的方法是采用动态规划，可以方便得出结论。动态规划常常适用于有重叠子问题和最优子结构性质的问题，法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

AC 代码

    public int change(int amount, int[] coins) {        int[] dp = new int[amount + 1];        dp[0] = 1;        for (int coin : coins) {            for (int i = coin; i <= amount; i++) {                dp[i] += dp[i - coin];            }        }        return dp[amount];    }

复制代码

总结

上述算法的时间复杂度是 O(n * n), 空间复杂度是 O(n)。
动态规划的题目需要多加练习，认真分析其中的子问题，才能掌握的更好！
坚持每日一题，加油！

发布于: 2021 年 06 月 10 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/ec8f050aae52a969adb370da4】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】零钱兑换 IIJava 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论