一、什么暴力递归可以继续优化？

有重复调用同一个子问题的解，这种递归可以优化

如果每一个子问题都是不同的解，无法优化也不用优化

二、暴力递归和动态规划的关系

某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划

任何动态规划问题，都一定对应着某一个有重复过程的暴力递归

但不是所有的暴力递归，都一定对应着动态规划

三、如何找到某个问题的动态规划方式？

1）设计暴力递归：重要原则+4种常见尝试模型！重点！

2）分析有没有重复解：套路解决

3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决

4）看看能否继续优化：套路解决

四、设计暴力递归过程的原则

1）每一个可变参数的类型，一定不要比int类型更加复杂

2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数

3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可

4）可变参数的个数，能少则少

五、常见的4种尝试模型

1）从左往右的尝试模型

2）范围上的尝试模型

3）多样本位置全对应的尝试模型

4）寻找业务限制的尝试模型

六、如何分析有没有重复解

列出调用过程，可以只列出前几层

有没有重复解，一看便知

七、暴力递归到动态规划的套路

1）你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
2）找到哪些参数的变化会影响返回值，对每一个列出变化范围
3）参数间的所有的组合数量，意味着表大小
4）记忆化搜索的方法就是傻缓存，非常容易得到
5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
6）对于有枚举行为的决策过程，进一步优化

八、动态规划的进一步优化

1）空间压缩

2）状态化简

3）四边形不等式

4）其他优化技巧

九、题目：机器人移动

假设有排成一行的N个位置，记为1~N，N一定大于或等于2
开始时机器人在其中的M位置上(M一定是 1~N中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N-1 位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数。

package class18;/*** 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2* 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)* 如果机器人来到1位置，那么下一步只能往右来到2位置；* 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；* 如果机器人来到中间位置，那么下一步可以往左走或者往右走；* 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种* 给定四个参数 N、M(cur)、K(rest)、P(aim)，返回方法数。*/
public class RobotWalk {//方法一：暴力递归public static int ways1(int N, int start, int aim, int K) {//边界判断 N至少要2个 机器人才能移动。 start开始位置和aim目标位置 范围在1-N，K步要大于0if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {//越界输入 直接返回-1return -1;}//调用递归函数，返回符合的从start移动k步到aim的次数return process1(start,K,aim,N);}/**** @param cur  机器人当前来到的位置cur* @param rest 机器人还有rest步要走* @param aim  最终要达到的目标位置aim* @param N    一共有N个位置*/public static int process1(int cur, int rest, int aim, int N){if(rest == 0){//base case:当步数都走完了的时候 判断cur当前位置是否来到aim 是则返回1种，否则就是0return cur == aim ? 1: 0;}//如果还有剩余步数 rest >0 那么判断几种情况的移动//当前cur在1位置时，只有向右+1 向左会越界 来到2  步数-1if(cur == 1){return process1(2,rest-1,aim,N);}//当前cur在N位置时，只能向左 -1 向右会越界  步数-1if(cur == N){return process1(N-1, rest - 1,aim,N);}//如果不在1 N 在中间 那么既可以向左 也可以向右 那么就表示有两种情况 返回就将两者相加return process1(cur-1,rest-1,aim,N) + process1(cur+1,rest-1,aim,N);}//优化方法二：添加缓存表 自顶向下的动态规划  也叫 记忆化搜索public static int ways2(int N,int start, int aim, int K){//边界判断 N至少要2个 机器人才能移动。 start开始位置和aim目标位置 范围在1-N，K步要大于0if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {//越界输入 直接返回-1return -1;}//方法一中 只跟cur rest相关 目标节点aim  n位置数 整个过程不影响//cur 当前位置范围是 1-N   rest 剩余步数 范围是 0-K//定义 二维数组 cur*rest 范围来保存这两个值的全部结果，作为缓存表作用 长度N+1 K+1 dp[0]行不处理 从1-N行处理即可int[][] dp = new int[N+1][K+1];for(int i = 0;i <= N;i++){for(int j = 0; j <= K;j++){//初始化赋值-1 表示还没访问到的位置dp[i][j] = -1;}}//从start开始位置移动K步 来到aim目标位置 传递dp保存访问结果 减少遍历次数 缓存表return process2(start,K,aim,N,dp);}public static int process2(int cur, int rest, int aim, int N, int[][]dp){//如果当前位置cur 剩余步数rest 得到的结果不是-1 就直接返回if(dp[cur][rest] != -1){//如果cur rest不是-1 说明已经访问过计算过结果了，直接返回 不用再计算return dp[cur][rest];}//定义一个结果集 用来返回int ans = 0;//情况1 剩余步数为0时if(rest == 0){//步数走完 当cur位置来到aim目标位置 说明符合题意次数 返回1  否则返回0ans = cur == aim ? 1 :0;}else if(cur == 1){//情况2 如果当前位置在1 还有剩余步数 那么只能向右走来到2 步数-1 赋值给ansans = process2(2,rest-1,aim,N,dp);}else if(cur == N){//情况3 剩余步数 cur在N 只能往左走ans = process2(N-1,rest-1,aim ,N,dp);}else{//情况4 不在头尾 那么就在中间 可以往左也可以往右ans = process2(cur+1,rest-1,aim,N,dp) + process2(cur-1,rest-1,aim,N,dp);}//赋值完成后，最后返回前 需要进行对缓存表的赋值dp[cur][rest] = ans;return ans;}//优化方法三：最终版动态规划 通过前面的递归加缓存表可以得到结果都是存放到一个二维数组//而目标就是根据前面的各种情况，填充这张表dp[N+1][K+1]，而结果返回的 根据题意要求cur当前位置 走了K步 就是dp[cur][rest]public static int ways3(int N,int start, int aim, int K){//边界判断 N至少要2个 机器人才能移动。 start开始位置和aim目标位置 范围在1-N，K步要大于0if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {//越界输入 直接返回-1return -1;}//方法一中 只跟cur rest相关 目标节点aim  n位置数 整个过程不影响//cur 当前位置范围是 1-N   rest 剩余步数 范围是 0-K//定义 二维数组 cur*rest 范围来保存这两个值的全部结果，作为缓存表作用 长度N+1 K+1 dp[0]行不处理 从1-N行处理即可int[][] dp = new int[N+1][K+1];   //默认值都是0//情况1 确定base case 当rest为0 时  只有cur==aim 值则为1 否则为0dp[aim][0] = 1;      //cur移动位置是行数，cur == aim 就在第aim行 第0列表示 rest没有剩余步数 此时值为1 该列其他位置都是0//当前rest剩余步数不为0时 则有多种情况for(int rest = 1; rest <= K; rest++) {//情况2 当cur位置来到1 时 机器人只能向右移动 来到2 也就是向下一行移动 并且剩余步数-1 向左一列移动 也就是依赖 左下位置的值dp[1][rest] = dp[2][rest-1];//情况3 当cur位置来到N 时 机器人只能向左移动 来到N-1 也就是向上一行移动 并且剩余步数-1 向左一列移动 也就是依赖 左上位置的值dp[N][rest] = dp[N-1][rest-1];//情况4 cur 不在1  N  机器人可以向左 向右移动 去到cur-1 cur+1 也就是上下一行的位置 剩余步数-1 左移一列 也就是以来 左下和左上位置的值for(int cur = 2; cur < N;cur++){dp[cur][rest] = dp[cur-1][rest-1] + dp[cur+1][rest-1];}}//把二维数组填充完成 最后题意要求的位置 就是在start位置到K步的值return dp[start][K];}public static void main(String[] args) {System.out.println(ways1(5, 2, 4, 6));System.out.println(ways2(5, 2, 4, 6));System.out.println(ways3(5, 2, 4, 6));}
}

十、题目：抽纸牌

给定一个整型数组arr，代表数值不同的纸牌排成一条线
玩家A和玩家B依次拿走每张纸牌
规定玩家A先拿，玩家B后拿
但是每个玩家每次只能拿走最左或最右的纸牌
玩家A和玩家B都绝顶聪明
请返回最后获胜者的分数。

package class18;/*** 给定一个整型数组arr，代表数值不同的纸牌排成一条线* 玩家A和玩家B依次拿走每张纸牌* 规定玩家A先拿，玩家B后拿* 但是每个玩家每次只能拿走最左或最右的纸牌* 玩家A和玩家B都绝顶聪明* 请返回最后获胜者的分数。*/
public class CardsInLine {//方法一：暴力递归 根据题意规则来写递归逻辑public static int win1(int[] arr) {if (arr == null || arr.length == 0) {return 0;   //base case 数组没有纸牌了都会被拿走时 为空 就返回0 分数}//调用 玩家A先拿者函数，返回玩家A的获胜分数//从数组开始0-最后一个索引 开始递归int first = f1(arr, 0, arr.length-1);//调用 玩家B后拿者函数，返回玩家B的获胜分数int second = g1(arr, 0, arr.length-1);//最后返回分数较大者return Math.max(first, second);}//玩家A先拿者 在数组L-R中获得的最好分数返回public static int f1(int[] arr, int L, int R) {if (L == R) {//base case 如果当前数组只有一个，那么玩家A是先手拿，那就返回当前该位置的分数return arr[L];}//如果不止一个 那么根据题意 可以从最左 最右 取牌//情况1：从左边取牌，那么剩下的就是L+1,R的牌 给玩家B后手拿 返回该情况的分数int p1 = arr[L] + g1(arr, L + 1, R);//情况2: 从右边取牌，那么剩下的就是L,R-1的牌 给玩家B后手拿 返回该情况的分数int p2 = arr[R] + g1(arr, L, R - 1);//两种情况，根据题意 玩家都是绝顶聪明 就会取两种情况较大值 作为自己的分数return Math.max(p1, p2);}//玩家B后拿者 在数组L-R中获得的最好分数返回public static int g1(int[] arr, int L, int R) {if (L == R) {return 0; //base case 如果当前只剩一张，因为这是玩家B后拿者，剩一张肯定是给玩家A先手拿了 所以就返回0}//如果不止一个，那么就判断情况//情况1 先手拿了L位置的牌，那么接着后手玩家B只能从 L-1,R中拿尽量分数最高的 就回到调用f1函数 该函数就是取分数最高的判断//相当与此时玩家B来到了玩家A的阶段int p1 = f1(arr, L + 1, R);//情况2 先手拿了R位置的牌，那么接着后手玩家B只能从 L,R-1中拿尽量分数最高的 就回到调用f1函数 该函数就是取分数最高的判断int p2 = f1(arr, L, R - 1);//情况分析完后，最后要返回玩家B后拿的最高分数，这里要考虑 取两者情况的较小值，因为f1()先手调用函数是会取最高分数的，而给到后//手时是分给后手各种情况中尽量少的分 所以返回两者较小值,这是被迫返回较小 因为题意要求玩家都是绝顶聪明，那么先手肯定是将分数高的给//自己，而给后手预留的就是尽量小的分数return Math.min(p1, p2);}//方法二：优化 缓存表  通过暴力递归函数的参数确定一个数组范围来填充结果public static int win2(int[] arr){if (arr == null || arr.length == 0) {return 0;   //base case 数组没有纸牌了都会被拿走时 为空 就返回0 分数}//根据L R的递归参数 定义一个二维数组 N行N列 N为arr的长度,注意这里是两个递归函数//分别定义两个二维数组 分开处理int N = arr.length;int[][] fmap = new int[N][N];int[][] gmap = new int[N][N];//初始化-1for(int i =0; i < N; i++){for(int j = 0; j < N; j++){fmap[i][j] = -1;gmap[i][j] = -1;}}//调用玩家A先手拿牌返回最好分数int first = f2(arr,0,N-1,fmap,gmap);//调用玩家B后手拿牌返回最好分数int second = g2(arr,0,N-1,fmap,gmap);//返回两者较大者return Math.max(first,second);}//玩家A先拿者 在数组L-R中获得的最好分数返回public static int f2(int[] arr, int L, int R,int[][]fmap, int[][]gmap){if(fmap[L][R] != -1){return fmap[L][R];  //base case:对应先拿玩家的二维数组 如果该位置不为-1 说明已经访问计算过 直接返回}//如果为-1 那么就表示首次计算访问 定义一个结果保存分数int ans = 0;//如果只有一个牌,先拿玩家肯定就会要这张牌 把值赋给ansif(L == R){ans = arr[L];}else {//如果不止一个牌 那么就可以取左边的牌 然后接着让后手玩家取L+1,R区间的牌的最好分数int p1 = arr[L] + g2(arr, L+1,R,fmap,gmap);//也可以取右边的牌....后手玩家取L,R-1int p2 = arr[R] + g2(arr,L,R-1,fmap,gmap);//那么就会取两者情况的较大者赋值给ansans = Math.max(p1,p2);}//最后返回ans,之前先把结果记录到fmap表中 后续就不需要再递归计算 直接取值返回fmap[L][R] = ans;return ans;}//玩家B后拿者 在数组L-R中获得的最好分数返回public static int g2(int[] arr, int L, int R, int[][]fmap, int[][]gmap){if(gmap[L][R] != -1){return gmap[L][R]; //base case:如果后者玩家表中已经访问计算过，那么就直接返回}//表为-1 说明首次访问 先定义一个结果int ans = 0;//按情况判断 如果只剩一张牌 那么这张牌只能给先手玩家取 而当前后手玩家则值为0if(L == R){ans = 0;}else{//如果不止一张，那么就是如果前手取L 后手只能从L+1,R取,而L被先手玩家取了 不能累加int p1 = f2(arr,L+1,R,fmap,gmap);//也可以前手取R  后手就是L,R-1范围取最好分数int p2 = f2(arr, L, R-1,fmap,gmap);//因为先手玩家聪明绝顶，肯定会选分数高的，然后剩下的会尽量返回较小的给后手 所以取两者情况较小值ans = Math.min(p1,p2);}//最后返回ans 前先给缓存表赋值gmap[L][R] = ans;return ans;}//方法三：最终动态规划  从前面找依赖 填充好二维表 最好直接返回public static int win3(int[] arr){if (arr == null || arr.length == 0) {return 0;   //base case 数组没有纸牌了都会被拿走时 为空 就返回0 分数}//根据L R的递归参数 定义一个二维数组 N行N列 N为arr的长度,注意这里是两个递归函数//分别定义两个二维数组 分开处理int N = arr.length;int[][] fmap = new int[N][N];int[][] gmap = new int[N][N];//初始化 根据前面情况L == R时，fmap玩家缓存表中值就是arr[L] 也就是二维数组的对角线值依次都是数组对应的下标值for(int i = 0; i< N;i++){fmap[i][i] = arr[i];}//而gmap玩家缓存表 L==R时 赋值的时0 数组初始值都是0 所以不用再赋值处理//接着判断情况 L <= R 才是正确的边界 左边不会大于右边 二维数组中 左下三角区就不需赋值 只需要关注右上三角区//看到如果不止一张牌时，先手玩家当前位置fmap[L][R] 它依赖的是arr[L] 或者arr[R] 以及后手玩家g函数gmap缓存表中 L+1,R  L,R-1 也就是对应gmap[L][R]的下一个位置和左一个位置//通过这个规律我们可以这样赋值两个表：// 第一列fmap[0][0]是对角线前面已经赋值过，那么再往右第二列，依次再往右下的对角线，进行赋值：//来到fmap[0][1] 其依赖的就是arr[L]+对应gmap[0][1]的gmap[1][1]    arr[R]+对应gmap[0][1]的gmap[0][0] 两者的较大值//所以根据这个规则 外层循环就是遍历 1-N列 每次都完成对应的对角线位置值，每次就是往右下位置，直到N列越界 就再从N=2开始遍历其右下位置整条对角线for(int startCol = 1; startCol < N; startCol++){//对角线startCol 0位置前面已经处理 从第一列开始//定义该次对角线的索引位置进行移动,每次都是从第一行开始的往右下遍历int L = 0;int R = startCol;while(R < N){//越界判断 当R列到N时就越界 而行是肯定不会先与列越界的 因为是在对角线上方，R列到最大N时，L行最多就是N-1行//开始给两个缓存表填充值 根据前面分析的规律//先手玩家 缓存表 当L!=R是分两者情况取最大值 取L左边的牌值加上后手玩家中L-1,R区间的牌值，     取R则加后手玩家L,R-1的牌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++;}}//最后缓存表都填充好数据 ，最后要返回的就是先手玩家0,N-1 已经后手玩家0,N-1的较大值return Math.max(fmap[0][N-1],gmap[0][N-1]);}public static void main(String[] args) {int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };System.out.println(win1(arr));System.out.println(win2(arr));System.out.println(win3(arr));}}