欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

322. 零钱兑换(难度:中等)

程序员文章站 2022-04-24 16:28:36
...

322. 零钱兑换(难度:中等)

题目链接:https://leetcode-cn.com/problems/coin-change/

问题描述:

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1

示例 1:

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

示例 2:

输入: coins = [2], amount = 3
输出: -1

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

解法一:动态规划 + 剪枝

首先,看见题目,我们一定先想到的是递归算法,我们分析这道题,他是具备 最优子结构 的。

最优子结构:

一个大问题的最优结果是由一堆子问题的最优结果推导出来的。比如我们要计算17的最少硬币数量,如果我们知道了16的最少硬币数是3枚(10,5,1),那么就把子问题的结果+1(再加一枚1元的硬币)就是原问题的答案。

满足的条件:硬币的数量没有现在,子问题之间没有任何限制,都是相互独立的。

重叠子问题:

应该在计算过程中,可能会对一个子问题进行反复的求解,比如我们可以会把子问题所需的最少硬币组成重复计算,这时候我们可以使用一个数组list来记录已经计算过的子问题结果,相当于一个备忘录的功能。

322. 零钱兑换(难度:中等)

状态转换方程:

我们分解子问题的过程,对原问题需要面值amout,每次选取一枚硬币面值t,然后使用硬币数目+1,再计算面值amout-t所需要的最少硬币数目。

当我们在分解子问题的过程中,可以会遇到以下几种情况:

(1)当子问题需要计算的面值为0,则不再需要硬币,返回0;

(2)当子问题需要计算的面值小于-1,显然是不满足条件的,返回-1;

(3)当子问题需要计算的面值大于0时,则所需硬币数+1,继续分解子问题。

322. 零钱兑换(难度:中等)

代码:

public class Solution {
  public int coinChange(int[] coins, int amount) {
    if (amount < 1) return 0;
    return coinChange(coins, amount, new int[amount]);
  }

  private int coinChange(int[] coins, int rem, int[] count) {
    if (rem < 0) return -1;
    if (rem == 0) return 0;
    if (count[rem - 1] != 0) return count[rem - 1];
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
      int res = coinChange(coins, rem - coin, count);
      if (res >= 0 && res < min)
        min = 1 + res;
    }
    count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
    return count[rem - 1];
  }
}