核心问题是穷举
因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。
递归的问题，都是树的问题，就是树的遍历。

特点：

  1. 穷举，存在大量的「重叠子问题」
  2. 具备「最优子结构」
  3. 列出正确的「状态转移方程」，穷举时问题可能变化，要确定好边界值


明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
步骤：

  1. 画树，找出重复子问题
  2. 写出子问题基本框架
  3. 找出边界值，最大最小值等
  4. 完善代码至可执行状态
  5. 优化代码，添加备忘录记录下重复处理的子问题答案，降低时间复杂度。

举例：
509. 斐波那契数
322. 零钱兑换

斐波那契数列

509. 斐波那契数

1.暴力递归

递归问题都是树的遍历问题，先把树画出来。
image.png
由图可得出，递归最基础的公式：动态规划 - 图2
再加上边界值，得出：
动态规划 - 图3

  1.     private static int test1(int n) {
  2.         if (n == 1 || n == 2) {
  3.             return 1;
  4.         }
  5.         return test1(n - 1) + test1(n - 2);
  6.     }

空间复杂度：动态规划 - 图4
时间复杂度：动态规划 - 图5,二叉树节点总数，指数级别。

2.带备忘录的递归解法

image.png
虽然暴力解法简单快捷，但是存在大量重复运算。
解法：把已计算过的数值记录起来，如哈希表、数组等。

2.1备忘录-哈希表

  1.     /**
  2.      * 2.备忘录 把已计算的值记录下来 (自顶向下)
  3.      */
  4.     private static int test2(int n) {
  5.         Map<Integer, Integer> map = new HashMap<>();
  6.         return test22(map, n);
  7.     }
  9.     private static int test22(Map<Integer, Integer> map, int n) {
  10.         if (n == 1 || n == 2) {
  11.             return 1;
  12.         }
  13.         if (map.containsKey(n)) {
  14.             return map.get(n);
  15.         }
  16.         int i = test22(map, n - 1) + test22(map, n - 2);
  17.         map.put(n, i);
  18.         return i;
  19.     }

递归过程中哈希表做了什么：
image.png
哈希表记录把二叉树指数级别的计算转化成线性级别的计算。
image.png
时间复杂度：动态规划 - 图9
空间复杂度：动态规划 - 图10

2.2备忘录-数组

image.png
本质上和用哈希表把二叉树指数级别转化成线性级别是一样的，只不过转换后的链表顺序相反。

  1.     /**
  2.      * 3.备忘录 把已计算的值记录下来 (自底向上)--数组
  3.      */
  4.     private static int test3(int n) {
  5.         if (n == 1 || n == 2) {
  6.             return 1;
  7.         }
  8.         int[] a = new int[n + 1];
  9.         a[1] = 1;
  10.         a[2] = 1;
  11.         for (int i = 3; i <= n; i++) {
  12.             a[i] = a[i - 1] + a[i - 2];
  13.         }
  14.         return a[n];
  15.     }

时间复杂度：动态规划 - 图12
空间复杂度：动态规划 - 图13

2.2优化备忘录

备忘录-数组我们发现，其实每次遍历仅仅需要n-1和n-2的值，n-3前的值已经是无用的，且遍历是有序递增。

  1.    /**
  2.      * 4.备忘录 把已计算的值记录下来 (自底向上)-- 只记录n-1和n-2有用的值
  3.      */
  4.     private static int test4(int n) {
  5.         if (n == 1 || n == 2) {
  6.             return 1;
  7.         }
  8.         int pre1 = 1;
  9.         int pre2 = 1;
  10.         int sum = 0;
  11.         for (int i = 3; i <= n; i++) {
  12.             sum = pre1 + pre2;
  13.             pre1 = pre2;
  14.             pre2 = sum;
  15.         }
  16.         return sum;
  17.     }

时间复杂度：动态规划 - 图14
空间复杂度：动态规划 - 图15, 只用到了pre1,pre2,sum

零钱兑换

斐波那契数列可能较为简单，还不需要完整的解题思路，零钱兑换这道题则可以很好地运用到一开始讲到的思路。

322. 零钱兑换

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

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

1.暴力递归

第一步：画树，找出子问题
image.png
核心问题：金额amount，至少需要n个币
伪代码：

  1.   //伪代码：
  2.   //step1:找出子问题的基本框架
  3.   int step1(int[] coins, int amount) {
  4.        int min = Integer.MAX_VALUE;
  5.         //在同一个子问题中，选取最优解（最小值）
  6.         for (int coin : coins) {
  7.             int res = step1(coins, amount - coin);
  8.             min = MIN(res,min)
  9.         }
  10.         //+1为需要币数量+1
  11.         return min+1;
  12.     }

第二步：找出边界值（base case）
这道问题的 base case 就是金额amount的值为0时，需要0个币，小于0时无解返回-1

  1.   //找出边界值，并完善代码
  2.   int step2(int[] coins, int amount) {
  3.         if (amount < 0) {
  4.             return -1;
  5.         }
  6.         //base case
  7.         if (amount == 0) {
  8.             return 0;
  9.         }
  10.        int min = Integer.MAX_VALUE;
  11.         //在同一个子问题中，选取最优解（最小值）
  12.         for (int coin : coins) {
  13.             int res = step1(coins, amount - coin);
  14.             //边界值找出后，对判断进行修改
  15.             if(res>=0 && res<min){
  16.                min = res;
  17.             }
  18.         }
  19.         //再处理边界问题，可能子问题一直无解
  20.         return (min == Integer.MAX_VALUE) ? -1 : min + 1;
  21.     }

以上完整的暴力解法已经出来，再加上备忘录降低时间复杂度。

2.递归-备忘录

  1.     /**
  2.      * 步骤三：添加备忘录降低时间复杂度
  3.      */
  4.     private static int step3(int[] coins, int amount) {
  5.         if (amount < 1) {
  6.             return 0;
  7.         }
  8.         return step33(coins, amount, new int[amount]);
  9.     }
  11.     private static int step33(int[] coins, int amount, int[] memos) {
  12.         if (amount < 0) {
  13.             return -1;
  14.         }
  15.         if (amount == 0) {
  16.             return 0;
  17.         }
  18.         //备忘录-有则直接返回
  19.         if (memos[amount-1] !=0){
  20.             return memos[amount-1];
  21.         }
  22.         int min = Integer.MAX_VALUE;
  23.         for (int coin : coins) {
  24.             int res = step33(coins, amount - coin, memos);
  25.             if (res < min && res >= 0) {
  26.                 min = res;
  27.             }
  28.         }
  29.         min = (min == Integer.MAX_VALUE) ? -1 : min + 1;
  30.         //插入备忘录
  31.         memos[amount-1] = min;
  32.         return min;
  33.     }

3.递归-备忘录-自底向上

数组大小为金额大小+1，从金额0开始算
image.png

动态规划 - 图18
动态规划 - 图19

0, 3, 4为5-5, 5-2, 5-1

  1.     private static int step44(int[] coins, int amount) {
  2.         if (amount < 0) {
  3.             return -1;
  4.         }
  5.         if (amount == 0) {
  6.             return 0;
  7.         }
  8.         //初始化备忘录，大小amount + 1
  9.         int[] memos = new int[amount + 1];
  10.         //初始化数组各个值为amount + 1
  11.         Arrays.fill(memos, amount + 1);
  12.         //第一个边界值0
  13.         memos[0] = 0;
  15.         for (int i = 0; i < amount + 1; i++) {
  16.             for (int coin : coins) {
  17.                 if (i - coin < 0) {
  18.                     //子问题无解，跳过
  19.                     continue;
  20.                 }
  21.                 memos[i] = Math.min(memos[i], 1 + memos[i - coin]);
  22.             }
  23.         }
  24.         return (memos[amount] == amount + 1) ? -1 : memos[amount];
  25.     }