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

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

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

接下来的几篇文章我们继续深挖动态规划的一些 优化策略。

通过前面文章的学习，相信小伙伴都能够根据不同模型的套路熟练的改出 严格表依赖 的动态规划版本了。

但有个问题？

记忆化搜索 和 严格 dp 表依赖 的时间复杂度一样，记忆化搜索的代码写起来容易，为什么还非要找到动态规划的 状态转移方程 ，进而修改成为严格表依赖关系的呢。接下来我们通过一道题目 揭晓答案 ！

找零钱问题Ⅰ

给定一个面值数组 arr ，其中的值均为无重复的正数，每一个值代表一种面值，张数无限。求能够组成 aim 的方法数是多少。

示例 1：

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

输出： 3

解释： 共三种组合方式

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

示例 2：

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

输出： 5

解释： 共五种组合方式

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

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

思路

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

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

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

代码

public static int coinsWay(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    return process(arr, 0, aim);
}

public static int process(int[] arr, int index, int rest) {
    if (index == arr.length) { 
        return rest == 0 ? 1 : 0;
    }
    int ways = 0;
    for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
        ways += process(arr, index + 1, rest - (zhang * arr[index]));
    }
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

代码解释

递归中，base case 为下标来到最后时，如果剩余的钱数为 0 ，说明前面的组合刚好能够凑出 aim 值，记为有效的一种情况。

选和不选 体现在 zhang 从 0 开始，直到该张数的面值超过了剩余钱数 rest 为止。继续调用递归且下标 index + 1 ，剩余钱数也相应减少。最终返回总的方法数即可。

---

写出该暴力版的递归之后修改出动态规划版的就很容易了。

动态规划版

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            int ways = 0;
            for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                ways += dp[index + 1][rest - (zhang * arr[index])];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码解释

可变的参数有两个：总的面值个数 N 和 剩余的目标钱数 rest 。因此，需要设置一个二维的 dp 表数组，由于 N, rest 的取值范围是 0~N 、0~aim ，因此数组大小设置为 dp[N + 1][aim + 1] 。

递归代码 index == arr.length 可知，初始只有 dp[N][0] 的值为 1 。

因为递归中只依赖 index + 1 的值，所以 dp 表倒着填写。

根据递归调用 process(arr, 0, aim) 可知最终返回 dp[0][aim] 。

---

之前的文章写到这里就结束了，但 这次不一样 ！

观察递归的代码，发现竟然有 3 层 for 循环。为什么呢？

思考后发现， dp 表中的每个位置同样需要 枚举 后才能知道（之前的题目能够直接计算出来）。那有没有办法消掉这层枚举的 for 循环呢？答案是有的！

下面我们通过画 dp 表，探寻该动态规划应如何进一步优化。

假设此时剩余的总钱数 rest = 10，面值数 arr[i] = 3 。

一图胜千言~

通过枚举代码可知，arr[i][10] 的值，红色 = 黄色 + 3 个紫色。

黄色：不选面值为 3 的钱币时，rest 仍为 10，依赖下一格 i + 1。

紫色：分别选 1 张、2 张、3张…时，rest 对应每次减 3 ，且依赖下一格 i + 1 行。

稍加思考发现，蓝色的位置即 arr[i][10 - 3] 位置的值正是 3 个紫色的总和。那么，就可以将 红色 = 黄色 + 3 个紫色，改为 红色 = 黄色 + 蓝色，这样就不需要一直往前寻找了，减少一个 for 循环。

最终优化版动态规划

public static int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= aim; rest++) {
            // 先令 红色 等于 黄色部分
            dp[index][rest] = dp[index + 1][rest];
            // 如果没越界，说明前面有蓝色部分，再加上蓝色部分
            if (rest - arr[index] >= 0) {
                dp[index][rest] += dp[index][rest - arr[index]];
            }
        }
    }
    return dp[0][aim];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意看越界的判断哦，黄色和蓝色分开加。这样就完成了最终版的动态规划~

回答最初的问题，为什么有了记忆化搜索还要写出严格的表依赖呢？

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

因此，前面学习的如何一步步的将暴力递归修改为严格表依赖动态规划的基础要打牢哦！还不会的赶快关注一下回顾前面的几篇文章吧！

~ 点赞 ~ 关注 ~ 不迷路 ~！！！

------------- 往期回顾 -------------
【算法 - 动态规划】原来写出动态规划如此简单！
【算法 - 动态规划】最长公共子序列问题
【算法 - 动态规划】最长回文子序列
【算法 - 动态规划】力扣 691. 贴纸拼词
【算法 - 动态规划】京东面试题 - 洗咖啡杯问题
【堆 - 专题】“加强堆” 解决 TopK 问题！
AC 此题，链表无敌！！！