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来记录已经计算过的子问题结果，相当于一个备忘录的功能。

状态转换方程：

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

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

（1）当子问题需要计算的面值为0，则不再需要硬币，返回0；

（2）当子问题需要计算的面值小于-1，显然是不满足条件的，返回-1；

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

image.png

代码：

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];
  }
}