前一篇咱们认真聊了聊递归，如果大伙都认真敲了相干代码，没有播种那是不可能的。同时敏锐的搭档可能也发现了，接下来咱们要说啥了——动静布局，对，终于终于咱们聊到动静布局了。

提到动静布局，不晓得你们第一反馈是啥，难？他人的帖子看不懂？这些都不是事儿，跟着我的步调一步一步往下走，等更完几篇文章之后，咱们再来总结的时候，那时，面对动静布局就不会再感觉难了。

以下注释：（本文篇幅仍旧较长，请急躁品尝）

一、暴力递归是啥

说直白点：暴力递归就是尝试

1、把问题转化为规模放大的同类问题的子问题

2、有明确的不须要持续进行递归的条件(base case)

3、有当失去了子问题的后果之后的决策过程

4、不记录每一个子问题的解

二、动静布局是啥

在递归调用过程中，动静布局会把已经的调用过程保留下来，下次遇到雷同的过程间接调用就行（空间换工夫）。也就是遇到有反复调用的递归过程，就能够应用动静布局进行优化。

拿咱们熟知的斐波那契数列举例。

斐波那契数列规定第一项是1，第二项是1，当前的每一项F(n) = F(n-1) + F(n-2)。

咱们开展求解第7项的过程如下：

咱们将求第7项的值开展后会发现，整个递归过程会有很多反复的过程，这时候咱们就能够应用动静布局进行优化求解。

在咱们求解过一次F(5)后，将其值存起来，下次再遇到需要求F(5)时间接取就能够了，缩小了反复求解的过程，同理，对于每一个求解过的值都这样做，这就是动静布局。

以上概念性的货色都太形象了，OK，来看两个理论的题目，认真感触感触从暴力递归到动静布局的魅力。

三、机器人挪动问题

1、题目形容

对于N个格子（从1~N标号），机器人最开始在Start（1<=Start<=N）地位，要求在走过K（K>=1）步后（一次一格），来到aim地位（1<=aim<=N），问机器人有多少种走法？

（注：在两端的格子只能往两头走，在两头的任意一个格子，能够抉择左走或右走）

2、思路1 从尝试开始

/** * 1.从尝试开始 * * @author Java和算法学习：周一 */public static int way1(int n, int start, int aim, int k) {    if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {        return -1;    }    return process1(start, k, aim, n);}/** * 计算机器人满足条件的走法有多少种 * * @param current   以后地位 * @param remaining 残余步数 * @param aim       指标地位 * @param n         格子数 */private static int process1(int current, int remaining, int aim, int n) {    // base case，不须要走时    if (remaining == 0) {        // 残余步数为0时以后正好在aim地位，则这是一种走法        return current == aim ? 1 : 0;    }    // 还有步数要走    if (current == 1) {        // 在最左侧，只能往右走        return process1(2, remaining - 1, aim, n);    } else if (current == n) {        // 在最右侧，只能往左走        return process1(n - 1, remaining - 1, aim, n);    } else {        // 在两头地位，左走或右走都能够，所以是两种状况产生的后果之和        return process1(current - 1, remaining - 1, aim, n)                + process1(current + 1, remaining - 1, aim, n);    }}

以上代码是依照题目要求写出的最合乎天然智慧的代码，也是最容易了解的代码。

3、思路2 傻缓存法优化

首先剖析这个调用过程是否有反复的步骤。

在递归调用的过程中，指标地位和格子数始终都是不变的，只有以后地位和残余步数始终在变，对于某次在格子6，残余步数为8的状况下剖析调用过程，如下：

会发现有反复的调用过程，所以这是能够用动静布局优化的，如果没有反复的调用过程，动静布局是优化不了的，也无奈优化。

定义一个缓存表的二维数组dp，机器人以后地位范畴是1\~n，残余步数范畴是0\~k，dp表(n + 1)*(k + 1)必定是可能将所有的状况都蕴含的。

最开始dp表均为-1，前面在递归调用时都先判断缓存表中是否有值，如果有（!=-1）间接返回值，没有才走递归过程，同时在每一次递归返回后果前都要更新缓存表dp。

/** * 2.傻缓存法 * * @author Java和算法学习：周一 */public static int way2(int n, int start, int aim, int k) {    if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {        return -1;    }    // 机器人以后地位范畴是1~n，残余步数范畴是0~k，dp表(n + 1)*(k + 1)必定是可能将所有的状况都蕴含的    int[][] dp = new int[n + 1][k + 1];    for (int i = 0; i <= n; i++) {        for (int j = 0; j <= k; j++) {            dp[i][j] = -1;        }    }    // dp[current][remaining] == -1，示意没算过    // dp[current][remaining] != -1，示意算过，保留的是产生的后果    return process2(start, k, aim, n, dp);}/** * 计算机器人满足条件的走法有多少种，傻缓存法 * * @param current   以后地位 * @param remaining 残余步数 * @param aim       指标地位 * @param n         格子数 */private static int process2(int current, int remaining, int aim, int n, int[][] dp) {    // 缓存表曾经有值了，间接返回    if (dp[current][remaining] != -1) {        return dp[current][remaining];    }    // 之前没算过    int answer;    if (remaining == 0) {        answer = current == aim ? 1 : 0;    } else if (current == 1) {        answer =  process2(2, remaining - 1, aim, n, dp);    } else if (current == n) {        answer =  process2(n - 1, remaining - 1, aim, n, dp);    } else {        answer =  process2(current - 1, remaining - 1, aim, n, dp)                + process2(current + 1, remaining - 1, aim, n, dp);    }    // 返回前更新缓存    dp[current][remaining] = answer;    return dp[current][remaining];}

因为此办法中递归调用过程是从顶向下的，所以此办法又叫从顶向下的动静布局。

同时，dp表中存在数据就间接返回，相似记忆，所以也叫记忆化搜寻。

傻缓存法是在暴力递归的过程上减少了一个dp数组，用于寄存之前产生的后果，所以把反复调用的过程优化了。然而，就完结了吗？必定不是。

4、最终版的动静布局

咱们画出第2种办法中的dp表。假如格子数n=5，start=2，aim=4，步数k=6。

从第1种办法的递归过程剖析如何填dp表

（1）因为格子数n=5，所以以后地位的范畴为1\~5，第0行应用不到，用“×”示意；因为步数k=6，残余步数范畴为0\~6；

public static int way1(int n, int start, int aim, int k) {    if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {        return -1;    }    return process1(start, k, aim, n);}

主函数调用递归函数时，求的是start=2、k=6的值，即(2, 6)的值，可得初始表如下

（2）残余步数为0时，以后地位为aim=4时为1，其余均为0；

// base case，不须要走时if (remaining == 0) {    // 残余步数为0时以后正好在aim地位，则这是一种走法    return current == aim ? 1 : 0;}

以后地位为1时，只能往第2格走，同时走一格残余步数减1（即依赖左下方格子的值）；以后地位为n=5时，只能往第n-1=4格走（即依赖左上方的值）；对于任意一个非边上的地位，能够往n-1和n+1格走（即依赖左下方和左上方的值）。可得dp表如下：

（3）据此，咱们能够依据从上往下从左往右的程序将整个表填完，如下所示

最初可得(2, 6)的值为13，即最初的后果是13。

（4）依据以上剖析，能够写出动静布局代码如下：

/** * 3.最终版的动静布局 * * @author Java和算法学习：周一 */public static int way3(int n, int start, int aim, int k) {    if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {        return -1;    }    // 机器人以后地位范畴是1~n，残余步数范畴是0~k，dp表(n + 1)*(k + 1)必定是可能将所有的状况都蕴含的    int[][] dp = new int[n + 1][k + 1];    // 残余步数为0时，以后地位为aim时为1    dp[aim][0] = 1;    for (int remaining = 1; remaining <= k; remaining++) {        // 第一行，依赖左下方的值        dp[1][remaining] = dp[2][remaining - 1];        // 第一行和第n行独自算后，此处就不必判断越界问题了        for (int current = 2; current <= n - 1; current++) {            // 非边上的行，依赖左下方和左上方的值            dp[current][remaining] = dp[current - 1][remaining - 1] + dp[current + 1][remaining - 1];        }        // 第n行，依赖左上方的值        dp[n][remaining] = dp[n - 1][remaining - 1];    }    return dp[start][k];}

看残缺个过程后，是不是恍然大悟，要是间接给你最初的代码，必定是不知所云，同时也不倡议去背这个动静规划表，动静规划表只是后果，不是起因。咱们从最开始的尝试开始，一步一步的往下推导，这就是状态转移的过程，想要一步间接写出最初的动静布局代码来是须要一直的练习和总结的。看到这里，置信大家都有播种了。

所有代码：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/dynamicprogramming/RobotWalk.java

趁热打铁，再来一题。

四、纸牌问题

1、题目形容

给定一个负数整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B顺次拿走每张纸牌（能够看见所有的牌），规定玩家A先拿，玩家B后拿。然而每个玩家每次只能拿走最左或最右的纸牌。玩家A和玩家B都绝顶聪明，请返回最初获胜者的分数。

2、思路1 从尝试开始

（1）剖析后手的状况

定义函数 f(arr, L, R)，示意后手在数组arr[L...R]上取得的最大分数。L、R是下标。

1）如果L==R，表明当初只剩下一张牌了，返回arr[L]即可；

2）否则，表明还剩不止一张牌，分两种状况

取L地位的，分数 = arr[L] + g[arr, L+1, R]（函数g是后手产生的最大分数）

取R地位的，分数 = arr[R] + g[arr, L, R-1]

因为我是后手，所以最初的分数是以上两种的最大值。

（2）剖析后手的状况

1）如果L==R，表明当初只剩下一张牌了，而此时我是后手，剩的一张被后手选了，我没得选，只能返回0；

2）否则，表明还剩不止一张牌，分两种状况

先手取L地位的，我后手分数 = f[arr, L+1, R]，即我以后手状态取[L+1, R]的最好分数；

先手取R地位的，我后手分数 = f[arr, L, R-1]，即我以后手状态取[L, R-1]的最好分数。

因为我是后手，大家都是绝顶聪明，所以先手必定只会留给我分数更少的后果，所以最初的分数是以上两种的最小值。

（3）代码

/** * 1.从尝试开始 * * @author Java和算法学习：周一 */public static int win1(int[] arr) {    if (arr == null || arr.length == 0) {        return 0;    }    int before = f1(arr, 0, arr.length - 1);    int after = g1(arr, 0, arr.length - 1);    return Math.max(before, after);}/** * 以先手状态取得的最大分数 */private static int f1(int[] arr, int L, int R) {    if (L == R) {        return arr[L];    }    // 还剩不止一张牌    int p1 = arr[L] + g1(arr, L + 1, R);    int p2 = arr[R] + g1(arr, L, R - 1);    return Math.max(p1, p2);}/** * 当前手状态取得的最大分数 */private static int g1(int[] arr, int L, int R) {    if (L == R) {        return 0;    }    // 对手拿走L地位的数    int p1 = f1(arr, L + 1, R);    // 对手拿走R地位的数    int p2 = f1(arr, L, R - 1);    return Math.min(p1, p2);}

3、思路2 傻缓存法优化

首先剖析是否有反复调用的过程

有反复调用过程，那么能够应用动静布局来优化。一直变动的是L和R的值，而在f函数外面又依赖g函数，g函数外面又依赖f函数，那么咱们无妨设计两个表。

/** * 2.傻缓存法 * * @author Java和算法学习：周一 */public static int win2(int[] arr) {    if (arr == null || arr.length == 0) {        return 0;    }    int N = arr.length;    int[][] fMap = new int[N][N];    int[][] gMap = new int[N][N];    for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            fMap[i][j] = -1;            gMap[i][j] = -1;        }    }    int before = f2(arr, 0, arr.length - 1, fMap, gMap);    int after = g2(arr, 0, arr.length - 1, fMap, gMap);    return Math.max(before, after);}/** * 以先手状态取得的最大分数 */private static int f2(int[] arr, int L, int R, int[][] fMap, int[][] gMap) {    if (fMap[L][R] != -1) {        return fMap[L][R];    }    int ans;    if (L == R) {        ans = arr[L];    } else {        // 还剩不止一张牌        int p1 = arr[L] + g2(arr, L + 1, R, fMap, gMap);        int p2 = arr[R] + g2(arr, L, R - 1, fMap, gMap);        ans =  Math.max(p1, p2);    }    // 更新缓存    fMap[L][R] = ans;    return fMap[L][R];}/** * 当前手状态取得的最大分数 */private static int g2(int[] arr, int L, int R, int[][] fMap, int[][] gMap) {    if (gMap[L][R] != -1) {        return gMap[L][R];    }    int ans;    if (L == R) {        ans = 0;    } else {        // 对手拿走L地位的数        int p1 = f2(arr, L + 1, R, fMap, gMap);        // 对手拿走R地位的数        int p2 = f2(arr, L, R - 1, fMap, gMap);        ans =  Math.min(p1, p2);    }    // 更新缓存    gMap[L][R] = ans;    return gMap[L][R];}

4、最终版的动静布局

首先剖析两个表的数据咋填的，假如arr = { 7, 4, 16, 15, 1 }；

（1）因为L<=R，所以表的左下方都不会用到，用“×”示意；同时fMap表，L==R时，值为arr[L]，即对角线顺次为数组的值；gMap表，L==R时，值为0。可得如下表

（2）剖析值的依赖状况

对于fMap(L, R)，依赖arr[L] + gMap(L + 1, R)和arr[R] + gMap(L, R - 1)的最大值;

对于gMap(L, R)，依赖fMap(L + 1, R)和fMap(L, R - 1)的最小值

如下图所示

（3）依据递归调用过程，可得最初的fMap和gMap如下图所示

看递归调用的起始传入的值，须要fMap[0, 4]和gMap[0, 4]的最大值即24。

（4）代码

/** * 3.最终动静布局 * * @author Java和算法学习：周一 */public static int win3(int[] arr) {    if (arr == null || arr.length == 0) {        return 0;    }    int N = arr.length;    int[][] fMap = new int[N][N];    int[][] gMap = new int[N][N];    for (int i = 0; i < N; i++) {        fMap[i][i] = arr[i];    }    for (int startColumn = 1; startColumn < N; startColumn++) {        // 行        int L = 0;        // 列        int R = startColumn;        while (R < N) {            fMap[L][R] = Math.max(arr[L] + gMap[L + 1][R], arr[R] + gMap[L][R - 1]);            gMap[L][R] = Math.min(fMap[L + 1][R], fMap[L][R - 1]);            L++;            R++;        }    }    return Math.max(fMap[0][N - 1], gMap[0][N - 1]);}

所有代码：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/dynamicprogramming/CardsInLine.java

从头认真看完的搭档，此刻对动静布局应该不那么胆怯了吧，加油！