Summary

1. 引入

本文主要内容就是描述将一个使用暴力递归解决的问题如何一步一步改成动态规划的。

暴力递归改dp

整体脉络是首先要找到一种尝试的方法，如果已经确定了尝试方法，就可以只通过尝试方法的本身来去做优化。尝试方法本身是和题目业务有关的，本质上就是一种递归的调度方式。在递归的调度方式确定了之后，接下来的优化和原始的递归含义是没有太大关系的，从递归的结构就能改出一个动态规划的版本。

从暴力递归改成动态规划的路线中，最好改的就是记忆化搜索的动态规划，暴力递归使用固定的策略就可以改出记忆化搜索的动态规划。
比记忆化搜索性能更好的就是严格表结构的动态规划，暴力递归也可以使用固定的策略改出严格表结构的动态规划。

在某些问题上，记忆化搜索的动态规划和严格表结构的动态规划有着相同的时间复杂度，但是严格表结构的动态规划由于已经推导出来位置依赖关系，由此可以在严格表结构的基础上进行更进一步的优化。

2. 题目：机器人运动

机器人运动

int型整数N，表示有N个位置（1~N）。
int型整数s，表示机器人一开始停在哪个位置。
int型整数e，表示机器人结束运动的位置。
int型整数k，表示机器人必须走k步。
整个模型就是一个机器人从 s 走 k 步到达 e，在走的过程中，可以向左走也可以向右走，但是不能越界和原地踏步。
比如说机器人来到 1 位置下一步只能向右走到 2 位置；机器人来到 N 位置下一步只能向左走到 N-1 位置。
一个机器人在只能走 k 步的情况下，从 s 到达 e ，一共有多少种走法？

2.1 暴力递归

public static int walkWays(int N, int s, int e, int k) {
    if (s < 1 || s > N || e < 1 || e > N || N < 1) {
        return 0;
    }

    return process(N, e, k, s);
}

/**
 * @param N 表示有N个位置（1~N）
 * @param e 表示机器人结束运动的位置
 * @param rest 还有多少步数
 * @param cur 当前位置
 * @return
 */
public static int process(int N, int e, int rest, int cur) {
    // basecase
    // 如果步数走完了，停止的位置如果在e位置则是一种走法，如果不在e位置则此种走法失败
    if (rest == 0) {
        return cur == e ? 1 : 0;
    }
    //rest 不是0，还可以走
    // 如果当前来到1，下一步只能走2
    if (cur == 1) {
        return process(N, e, rest - 1, 2);
    }

    // 如果当前来到N，下一步只能走N-1
    if (cur == N) {
        return process(N, e, rest - 1, N - 1);
    }

    // 如果当前来到到既不是1，也不是N，下一步既可以向左走，也可以向右走
    return process(N, e, rest - 1, cur - 1) + process(N, e, rest - 1, cur + 1);
}

由如上对于递归方法的设计，有4个参数，前两个 N 和 e 是固定参数，后两个 rest 和 cur 是可变参数。
固定参数对递归方法的状态没有影响，可变参数是描述递归状态的唯一指标，因此只要确定了方法的可变参数，就相当于确定了递归方法什么时候结束。

那么我们思考一下这个递归方法被我们以什么样的方式调用呢？
我们首先将该递归方法简化，省略两个固定参数，只保留两个可变参数，假设为：p( int rest，int cur )。
按照原题还是从 p( 4，2 )，我们来分析一下递归调用过程：

递归简化

如图所示，在递归调用过程中，调用到 P( 2，2 ) 时，需要将 P( 2，2 ) 继续递归展开，直到完全展开到最底层的情况后依次向上汇总，才能得到 P( 2，2 ) 的值。而计算完一个 P( 2，2 ) ，下次再次遇到 P( 2，2 ) 时，还是得按照上面的流程将 P( 2，2 ) 递归展开，这样一点都没有必要，进行了大量的重复计算，这就是为什么此方法被称为暴力递归。

暴力递归解决该问题的时间复杂度如何估算？
最差情况是机器人当前位置在可运动范围的中间，机器人每一步都可以向左走或者向右走，整个递归调用过程可以整体看作是一棵深度为 k 的二叉树，因此时间复杂度为O(2^k)。

如果存在一个表结构，将 P( 2，2 ) 这个递归过程的计算结果记录到这个表结构中，如果再次遇到 P( 2，2 ) 就可以直接从这个表结构中拿结果，不需要再将 P( 2，2 ) 递归展开了。
也就是说，我们使用了更多的空间，来减少暴力递归的时间。

那么现在还有一个问题，就是只要确定了递归方法的可变参数，那么就能一定能确定返回值嘛？也就是说如上图所示，P( 3，1 ) 调用的 P( 2，2 ) 和 P( 3，3 ) 调用的 P( 2，2 )，这两个 P( 2，2 ) 的返回值一样嘛？
一样。具备这种特性的尝试叫做无后效性尝试，也就是说之前的决定不会影响后面决定的结果。这种尝试类型非常适合改成动态规划。

一般在面试过程中出的动态规划题目都可以写出无后效性尝试方法。

2.2 记忆化搜索DP

记忆化搜索相当于在原来暴力递归的基础上添加缓存结构，这个缓存结构就是后面所说的dp表。

有几个可变参数就创建一个几维的dp表。
确定每个可变参数的变化范围，从而确定dp表的规模，也就是dp表各个维度的初始容量。
- 一般情况下，假如一个可变参数的变化范围是 1~N，那么我们会给该参数在dp数组中的对应维度开 N+1 的初始空间，该维度的第 0 位我们不会去使用，只使用第 1 位到第 N 位的空间。
将dp表的每一个位置初始化。一般情况下，都初始化为 -1，-1 表示该位置所代表的递归状态没有被计算过。
将dp表加入原递归方法的形参列表，作为参数之一。让递归方法带着dp表一起递归。
使用缓存结构，具体使用方法为：如果当前递归状态所对应的dp表位置的值不是 -1，缓存命中，那么直接返回dp表对应位置的值。
建立缓存结构，具体建立方法为：如果当前递归状态所对应的dp表位置的值是 -1，缓存没有命中，将计算结果存入dp表对应位置，再继续递归展开。

public static int walkWays(int N, int s, int e, int k) {
    if (s < 1 || s > N || e < 1 || e > N) {
        return 0;
    }
    
    // 一维是还有几步结束，二维是当前位置
    int[][] dp = new int[k + 1][N + 1];

    // 初始化缓存
    for (int i = 0; i <= k; i ++) {
        for (int j = 0; j <= N; j ++) {
            dp[i][j] = -1;
        }
    }

    return process(N, e, k, s, dp);
}

/**
 * @param N 表示有N个位置（1~N）
 * @param e 表示机器人结束运动的位置
 * @param rest 还有多少步数
 * @param cur 当前位置
 * @param dp 缓存结构
 * @return
 */
public static int process(int N, int e, int rest, int cur, int[][] dp) {
    // 命中缓存
    if (dp[rest][cur] != -1) {
        return dp[rest][cur];
    }
    
    // 没有命中缓存
    // basecase
    // 如果步数走完了，停止的位置如果在e位置则是一种走法，如果不在e位置则此种走法失败
    if (rest == 0) {
        dp[rest][cur] = cur == e ? 1 : 0;
    }
    // 如果当前来到1，下一步只能走2
    else if (cur == 1) {
        dp[rest][cur] = process(N, e, rest - 1, 2, dp);
    }
    // 如果当前来到N，下一步只能走N-1
    else if (cur == N) {
        dp[rest][cur] = process(N, e, rest - 1, N - 1, dp);
    }
    // 如果当前来到到既不是1，也不是N，下一步既可以向左走，也可以向右走
    else {
        dp[rest][cur] = process(N, e, rest - 1, cur - 1, dp) + process(N, e, rest - 1, cur + 1, dp);
    }

    return dp[rest][cur];
}

记忆化搜索解决该问题的时间复杂度如何估算？

dp表的规模是 k×N，dp表中的 k×N 个位置在计算时只计算一次，同一个位置在重复访问时直接返回，代价是O(1)，因此记忆化搜索解决该题的时间复杂度是O(k×N)。

2.3 严格表结构DP

严格表结构的动态规划就不需要使用递归了，也不需要将dp表中每个位置都初始化为 -1 了，我们通过找到位置与位置的依赖关系，然后规定好依赖的顺序，最后使用迭代的方式将暴力递归版本中调用递归函数的代码改成dp表的替代即可。

在改成严格表结构的动态规划的过程中建议边画图边分析，如下先将架子搭好：

严格表结构

分析dp表中有哪些位置是无效的
无效位置有的题有，有的没有。有的话在遍历时直接跳过，不需要初始值。
通过原递归方法中的basecase，分析dp表中有哪些位置是能够直接得到答案的

直接得到答案

if (rest == 0) {
    return cur == e ? 1 : 0;
}

由代码可得：e = 4，当 rest = 0 && cur = 4 时可以直接得到 dp[0][4] = 1；当 rest = 0 && cur != 4 && cur != 0 时可以直接得到 dp[0][cur] = 0。--basecase

通过题意，确定终止位置
在本题中，rest = 4 && cur = 2 是终止位置，在 dp[4][2] 上做个标记。

确定终止位置

终止位置也是由直接得到答案的位置通过位置依赖最终要推向的位置。

通过原递归方法推出边界位置的值的位置依赖

dp[rest][1] 都依赖 dp[rest - 1][2]:

if (cur == 1) {
    return process(N, e, rest - 1, 2);
}

如下代码推出：dp[rest][N] 都依赖 dp[rest - 1][N - 1]:

if (cur == N) {
    return process(N, e, rest - 1, N - 1);
}

推出位置依赖后，边界位置的值可以通过位置依赖直接将依赖位置的值拷贝到自身即可。

边界位置依赖

通过原递归方法推出普遍位置的值的位置依赖
如下代码推出：dp[rest][cur] = dp[rest - 1][cur - 1] + dp[rest - 1][cur + 1]

return process(N, e, rest - 1, cur - 1) + process(N, e, rest - 1, cur + 1);

普遍位置依赖

确定依赖计算的顺序
因为本题中每个位置的依赖要不然依赖相邻行的左上方的位置或右上方的位置，要不然同时依赖相邻行的左上方的位置和右上方的位置，所以本题中依赖计算的顺序是从上到下，从左到右。

其实从上到下，从右到左也是可以的，因为同一行各个位置之间没有位置依赖关系。如下题目如果同一行没有位置依赖关系，就不特殊指出了，默认为从左到右。

通过位置依赖关系和依赖计算顺序，dp中每一个位置的值都能直接得到，一直推到终止位置，得到答案

严格表结构答案

public static int walkWays(int N, int s, int e, int k) {
    if (N < 1 || s < 1 || s > N || e < 1 || e > N) {
        return 0;
    }

    int[][] dp = new int[k + 1][N + 1];

    // 当cur==0时，无论rest是多少都是不符合题意的，全部置-1
    for (int rest = 0; rest <= k; rest ++) {
        dp[rest][0] = -1;
    }

    // 当rest==0时，无论cur是都少都可以直接得到是否到达终点的判断
    for (int cur = 1; cur <= N; cur ++) {
        dp[0][cur] = 0;
    }
    dp[0][4] = 1;

    // 从上往下，从左往右根据位置依赖关系填表
    // cur==0和rest==0的情况已被规避
    for (int rest = 1; rest <= k; rest ++) {
        for (int cur = 1; cur <= N; cur ++) {
            if (cur == 1) {
                dp[rest][cur] = dp[rest - 1][2];
            } else if (cur == N) {
                dp[rest][cur] = dp[rest - 1][N - 1];
            } else {
                dp[rest][cur] = dp[rest - 1][cur - 1] + dp[rest - 1][cur + 1];
            }
        }
    }

    return dp[4][2];
}

严格表结构的动态规划和记忆化搜索是有区别的，记忆化搜索不整理位置之间的依赖关系，而严格表结构的动态规划是需要考虑位置之间的依赖顺序的。

严格表结构的动态规划解决该问题的时间复杂度如何估算？
从dp表的确定值通过位置依赖一步步推到初始位置的代价就是整体的时间复杂度。得到每个位置的值的代价是O(1)，dp表的规模是 k×N，因此严格表结构的动态规划解决该题的时间复杂度也是O(k×N)。记忆化搜索的方法和严格表结构的动态规划方法等效。

为什么到现在没有出现状态转移方程？
状态转移方程就是暴力递归中尝试的方法，只要确定尝试方法，状态转移方程就出来了。千万不要反着想，看到题目先去列状态转移方程。如果这样去学，永远搞不定动态规划，因为你对尝试的模型一点都不熟悉。一定要从最初的暴力递归一步一步稳扎稳打到最终写出优化版本才是学动态规划最好的路线，不要去想状态转移方程，新手也很难写出状态转移方程。

3. 最小硬币问题

有一个正数数组coins存放当前拥有的所有硬币，数组中每一个位置代表一枚硬币，每一个位置的值是该硬币的面额，有可能有重复值。现在给你一个总额total，求出最少用多少硬币能够正好凑出total？
假如当前 coins = { 2，7，3，5，3 }，total = 10；则求出最少使用 2 枚硬币（7 + 3）可以凑出total。

3.1 暴力递归

该题的尝试方法就是从左往右每一个硬币选择要还是不要，最终决策出一个最少硬币且能正好凑出total的方案的硬币数。

public static int minCoins(int[] coins, int total) {
    if (coins == null || coins.length == 0) {
        return 0;
    }

    return process(coins, 0, total);
}

/**
 * @param coins 存放硬币的数组
 * @param coinIndex 当前硬币的在数组中的下标
 * @param restMoney 要凑整total还需要的钱数
 * @return 当前决策路径需要的最少的硬币数
 */
public static int process(int[] coins, int coinIndex, int restMoney) {
    // basecase1
    // 如果该条尝试路径还有硬币没有选择，就已经凑不整total了，该条尝试路径失败
    if (restMoney < 0) {
        return -1;
    }
    
    // basecase2
    // 如果该条路径正好凑整total，该条路径成功，当前不需要再选择硬币，直接返回
    if (restMoney == 0) {
        return 0;
    }
    
    // basecase3
    // 如果该条尝试路径所有硬币都可以选择，但还是没有凑整total，该条尝试路径失败
    if (restMoney > 0 && coinIndex == coins.length) {
        return -1;
    }

    // 如果该条尝试路径还有硬币没有选择，还没有凑整total，做决策

    // 不选择当前硬币
    int p1 = process(coins, coinIndex + 1, restMoney);
    // 选择当前硬币
    int p2 = process(coins, coinIndex + 1, restMoney - coins[coinIndex]);

    // 无论选不选当前硬币都不能成功凑出total
    if (p1 == -1 && p2 == -1) {
        return -1;
    } else {
        // 不选择当前硬币不能凑出total，选择当前硬币可以凑出total
        if (p1 == -1) {
            return p2 + 1;
        }
        // 不选择当前硬币可以凑出total，选择当前硬币不能凑出total
        else if (p2 == -1) {
            return p1;
        }
        // 不选择当前硬币和选择当前硬币都可以凑出total
        else {
            return Math.min(p2 + 1, p1);
        }
    }
}

3.2 记忆化搜索DP

由如上对于递归方法的设计，有3个参数，第一个参数 coins 是固定参数，后两个 coinIndex 和 restMoney 是可变参数。

在将暴力递归版本改成记忆化搜索的版本步骤和上面一致，需要注意的点是：

在确定dp表规模的时候，dp表的二维所代表的 restMoney 是可能会小于 0 的，可以认为dp表的纵坐标 rest = 0 左侧全都是 -1，但是不需要在dp表中进行实现。因此可以将如下代码放到判断缓存是否命中操作的上方，相当于是一个硬逻辑。同样也相当于是一个缓存，但是无需和dp表进行交互，只是人为想象的缓存，相当于如下代码和判断缓存是否命中的代码共同组成一个完整的判断缓存是否命中的代码。
在初始化dp表的时候，因为 -1 在解决过程中都有实际的含义，表示算过，但是无效解，所以可以将dp表的所有位置初始化为 -2。

public static int minCoins(int[] coins, int total) {
    if (coins == null || coins.length == 0) {
        return 0;
    }

    int[][] dp = new int[coins.length + 1][total + 1];

    for (int i = 0; i <= coins.length; i ++) {
        for (int j = 0; j <= total; j ++) {
            dp[i][j] = -2;
        }
    }

    return process(coins, 0, total, dp);
}


/**
 * @param coins 存放硬币的数组
 * @param coinIndex 当前硬币的在数组中的下标
 * @param restMoney 要凑整total还需要的钱数
 * @param dp 缓存结构
 * @return 当前决策路径需要的最少的硬币数
 */
public static int process(int[] coins, int coinIndex, int restMoney, int[][] dp) {
    // 三个都是basecase
    // 如果该条尝试路径还有硬币没有选择，就已经凑不整total了，该条尝试路径失败
    if (restMoney < 0) {
        return -1;
    }

    // 判断缓存是否命中
    if (dp[coinIndex][restMoney] != -2) {
        return dp[coinIndex][restMoney];
    }

    // 如果该条路径正好凑整total，该条路径成功，当前不需要再选择硬币，直接返回
    if (restMoney == 0) {
        dp[coinIndex][restMoney] = 0;
    }
    // 如果该条尝试路径所有硬币都可以选择，但还是没有凑整total，该条尝试路径失败
    else if (restMoney > 0 && coinIndex == coins.length) {
        dp[coinIndex][restMoney] = -1;
    }
    // 如果该条尝试路径还有硬币没有选择，还没有凑整total，做决策
    else {
        // 不选择当前硬币
        int p1 = process(coins, coinIndex + 1, restMoney, dp);
        // 选择当前硬币
        int p2 = process(coins, coinIndex + 1, restMoney - coins[coinIndex], dp);

        // 无论选不选当前硬币都不能成功凑出total
        if (p1 == -1 && p2 == -1) {
            dp[coinIndex][restMoney] = -1;

        } else {
            // 不选择当前硬币不能凑出total，选择当前硬币可以凑出total
            if (p1 == -1) {
                dp[coinIndex][restMoney] = p2 + 1;
            }
            // 不选择当前硬币可以凑出total，选择当前硬币不能凑出total
            else if (p2 == -1) {
                dp[coinIndex][restMoney] = p1;
            }
            // 不选择当前硬币和选择当前硬币都可以凑出total
            else {
                dp[coinIndex][restMoney] = Math.min(p2 + 1, p1);
            }
        }
    }
    
    return dp[coinIndex][restMoney];
}

3.3 严格表结构

假设：coins[] = { 2，3，5，7，2 }，total = 10。

通过原递归方法中的basecase，分析dp表中有哪些位置是能够直接得到答案的

if (restMoney < 0) {
  return -1;
}

if (restMoney == 0) {
  return 0;
}

if (restMoney > 0 && coinIndex == coins.length) {
  return -1;
}

分析basecase

通过题意，确定终止位置

在本题中，coinIndex = 0 && restMoney = 10 是终止位置，在 dp[0][10] 上做个标记，最终要返回 dp[0][10] 的值。