【算法 - 动态规划】找零钱问题Ⅱ

在前面���动态规划系列文章中，关于如何对递归进行分析的四种基本模型都介绍完了，再来回顾一下：

1. 从左到右模型 ：arr[index ...] 从 index 之前的不用考虑，只考虑后面的该如何选择 。
2. 范围尝试模型 ：思考 [L ,R] 两端，即 开头和结尾 处分别该如何取舍。
3. 样本对应模型 ：以 结尾位置 为出发点，思考两个样本的结尾都会产生哪些可能性 。
4. 业务限制模型 ：不能够明确的知道一个参数的变化范围，通过业务的限制找到 最差情况 进行估计。

上篇文章我们深挖了动态规划的一些 优化策略 ，并回答开篇提到的问题，为什么有了 记忆化搜索 还要找到动态规划的 状态转移方程 ，进而修改成为 严格的表依赖 呢：

消除枚举行为多产生的 for 循环，有了 表依赖 才能找到如何 优化枚举 ！。

接下来我们继续练习一道与上篇非常相似的题目，只需稍加修改即可！

找零钱问题Ⅱ

给定一个 货币 数组 arr ，其中的值均为正数，每一个值代表一张货币，值相同的货币没有任何不同。求能够组成 aim 的方法数是多少。

示例 1：

输入: arr = {1, 2, 1, 2, 1, 2, 1} ，aim = 4 。

输出： 3

解释： 共三种组合方式

• 1 + 1 + 1 + 1 = 4
• 1 + 1 + 2 = 4
• 2 + 2 = 4

  示例 2：

  输入: arr = {1, 2, 2, 2, 5} ，aim = 6 。

  输出： 2

  解释： 共两种组合方式

  • 2 + 2 + 2 = 6
  • 1 + 5 = 6

    ---

    注意： 要区分好与 上一篇文章中零钱问题 的区别哦！

    • 两篇文章共性：相同面值货币无区别
    • 上篇文章零钱问题Ⅰ：张数不限
    • 本篇文章零钱问题Ⅱ：张数有限

      在学会了上篇文章 后，本道题目就呼之欲出了（思路几乎一模一样）。

      首先我们依然采用最朴素的 暴力递归 来思考这道题目。

      思路

      这道题就是典型的 从左到右模型 ，因此，递归就可以按照 在 arr[index ...]数组中，index 之前的不用考虑，只考虑后面的该如何选择 的思路来划分情况：

      • 当前 index 下标对应的面值 参与 组合，选择任意张数，之后能有多少种情况；
      • 当前 index 下标对应的面值 不参与 组合，选择任意张数，之后能有多少种情况。

        因为要求总的情况，因此要返回这两种情况的 总和 。

        与上道题不同的是： 本题的货币张数有限制。因此，我们需要构建一个货币的信息结构体用来存储每种货币以及对应的张数。

        统计知道货币的张数之后，只需在循环时多加一个限制条件即可。

        代码

        // 每种面值货币的结构体public static class Info {    public int[] coins;    public int[] zhangs;    public Info(int[] coin, int[] zhang) {        coins = coin;        zhangs = zhang;    }}public static Info getInfo(int[] arr) {    // 统计出有多少种货币    HashMap counts = new HashMap();    for (int value : arr) {        if (!counts.containsKey(value)) {            counts.put(value, 1);        } else {            counts.put(value, counts.get(value) + 1);        }    }    // 总共有 N 种货币    int N = counts.size();    int[] coins = new int[N];    int[] zhangs = new int[N];    int index = 0;    // 统计出货币的张数    for (Entry entry : counts.entrySet()) {        coins[index] = entry.getKey();        zhangs[index++] = entry.getValue();    }    return new Info(coins, zhangs);}public static int coinsWay(int[] arr, int aim) {    if (arr == null || arr.length == 0 || aim