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

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

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