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

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

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

一、暴力递归是啥

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

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

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