写点什么

头脑风暴:零钱兑换 3

  • 2022 年 8 月 15 日
    江苏
  • 本文字数:805 字

    阅读完需:约 3 分钟

头脑风暴:零钱兑换3

题目

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。


计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。


你可以认为每种硬币的数量是无限的。


示例 1:


输入:coins = [1, 2, 5], amount = 11输出:3 解释:11 = 5 + 5 + 1
复制代码


示例 2:


输入:coins = [2], amount = 3输出:-1
复制代码


示例 3:


输入:coins = [1], amount = 0输出:0
复制代码


提示:


  • 1 <= coins.length <= 12

  • 1 <= coins[i] <= 2^31 - 1

  • 0 <= amount <= 10^4

解题思路

根据题意,本题可采用动态规划的方式来求解。


第一步,确定 dp 数组以及下标的含义:


dp[j]:凑足总额为 j 所需钱币的最少个数为 dp[j]。


第二步,确定递推公式:分俩种情况:第一种,dp[j],考虑 coins[i],那只有从 dp[j - coins[i]] 来推导;第二种,凑足总额为 j - coins[i] 的最少个数为 dp[j - coins[i]],那么只需要加上一个钱币 coins[i],表达式为 dp[j - coins[i]] + 1。


所以 dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。


递推公式为:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);


第三步,dp 数组初始化:


dp[0] = 0。


第四步,确定遍历顺序:


本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数。

代码实现

class Solution {    public int coinChange(int[] coins, int amount) {        int max = amount + 1;        int[] dp = new int[amount + 1];        Arrays.fill(dp, max);        dp[0] = 0;        for (int i = 1; i <= amount; i++) {            for (int j = 0; j < coins.length; j++) {                if (coins[j] <= i) {                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);                }            }        }        return dp[amount] > amount ? -1 : dp[amount];    }}
复制代码

最后

  • 时间复杂度:O(Sn),其中 S 是金额,n 是面额数。

  • 空间复杂度:O(S)。

发布于: 刚刚阅读数: 2
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
头脑风暴:零钱兑换3_算法_HelloWorld杰少_InfoQ写作社区