算法拾遗二十三之暴力递归到动态规划一

• • • 题目一
    • • 优化Code（空间换时间）
      • • 优化二
    • 题目二
    • • 优化一（缓存法）
      • 优化三（严格表优化）

题目一

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

方法一：

/**** @param N 一共有多少个位置* @param start 开始位置* @param aim 目标位置* @param K 移动步数* @return*/public static int ways1(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);}// 机器人当前来到的位置是cur，// 机器人还有rest步需要去走，// 最终的目标是aim，// 有哪些位置？1~N// 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？public static int process1(int cur, int rest, int aim, int N) {if (rest == 0) { // 如果已经不需要走了，走完了！//如果当前的位置等于aim位置则方案数加一，否则方案数不变return cur == aim ? 1 : 0;}//rest > 0，还有步数要走// (cur, rest)if (cur == 1) { // 1 -> 2return process1(2, rest - 1, aim, N);}// (cur, rest)if (cur == N) { // N-1 <- Nreturn process1(N - 1, rest - 1, aim, N);}//机器人停在中间位置上// (cur, rest)return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);}

优化Code（空间换时间）

假设我们机器人从七位置触发可以走十步，然后到13位置结束，可以画出如下模型图

可以看到从7位置出发还有八步要走是个重复值。从而推导cur和rest这两个值是决定最终返回值的key，所以可以采用缓存法

public static int ways2(int N, int start, int aim, int K) {if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {return -1;}// N+1 * K+1 规模int[][] dp = new int[N + 1][K + 1];//初始化dp缓存表for (int i = 0; i <= N; i++) {for (int j = 0; j <= K; j++) {dp[i][j] = -1;}}// dp就是缓存表// dp[cur][rest] == -1 -> process1(cur, rest)之前没算过// dp[cur][rest] != -1 -> process1(cur, rest)之前算过，返回值，dp[cur][rest]// N+1 * K+1return process2(start, K, aim, N, dp);}/**** @param cur 范围: 1 ~ N* @param rest 范围：0 ~ K* @param aim* @param N* @param dp* @return*/public static int process2(int cur, int rest, int aim, int N, int[][] dp) {//先查缓存表，如果不等于-1表示我之前算过这种情况if (dp[cur][rest] != -1) {return dp[cur][rest];}// 之前没算过，则在此处进行计算int ans = 0;if (rest == 0) {ans = cur == aim ? 1 : 0;} else if (cur == 1) {ans = process2(2, rest - 1, aim, N, dp);} else if (cur == N) {ans = process2(N - 1, rest - 1, aim, N, dp);} else {ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);}//返回之前记录此时答案dp[cur][rest] = ans;return ans;}

优化二

如下图：
机器人在2位置，他要到4位置只能走六步，N=5;

先填入basecase
if(rest == 0) cur ==aim ? 1 : 0;

然后由如上的代码我们知道最终要的位置是start 和k，主函数最终调的是start和k这个返回值。

再分析暴力递归代码，找到依赖关系，cur来到1，则依赖值来到cur在2但是rest-1的位置：


依赖关系如上图。

再来看cur==N，依赖值来到cur=N-1的位置，rest=rest-1的位置


如果是其他位置，则依赖关系如下：

依赖关系如下图：

如上三种情况的依赖关系都有了那么则根据依赖关系来填入这张表：

最终得到2，6的位置为13

 public static int ways3(int N, int start, int aim, int k) {if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {return -1;}int[][] dp = new int[N + 1][k + 1];dp[aim][0] = 1;for (int rest = 1; rest <= k; rest++) { //列//第一行dp[1][rest] = dp[2][rest - 1];for (int cur = 2; cur < N; cur++) {dp[cur][rest] = dp[cur-1][rest-1] + dp[cur+1][rest-1];}//最后一行dp[N][rest] = dp[N - 1][rest - 1];}return dp[start][k];}

题目二

给定一个整型数组arr，代表数值不同的纸牌排成一条线玩家A和玩家B依次拿走每张纸牌规定玩家A先拿，玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩家B都绝顶聪明请返回最后获胜者的分数【按照最优的方式做决策】。
例：
有如下数组
【50，100，20，10】
先手：10，100
后手：50，20
最后返回110获胜者分数。

思路：
先手：
函数给定f(arr,L,R)这个范围上面拿牌，最后我能获得的最好分数
是多少返回
basecase：
if(L==R) {
只剩一张牌了 return arr[L]
}
第一种选择arr[L] + g(arr,L+1,R)【以后手姿态拿走的牌】
第二种选择arr[R] + g(arr,L,R-1)【以后手姿态拿走的牌】
最后求一个max出来。

后手：
if(L==R) {
return 0;
}
第一种选择，如果对手拿走arr【L】那么后手就在f(arr,L+1,R)先手
第二种选择，如果对手拿走了arr【R】那么后手就在f(arr,L,R-1)先手

	//根据规则返回获胜者的分数public static int win1(int[] arr) {if(arr == null || arr.length == 0) {return 0;}int first = f(arr,0,arr.length-1);int second = g(arr,0,arr.length-1);return Math.max(first,second);}//arr[L..R]，先手获得的最好分数返回public static int f(int[] arr,int L,int R) {if(L == R) {return arr[L];}int p1 = arr[L] + g(arr,L+1,R);int p2 = arr[R] + g(arr,L,R-1);return Math.max(p1,p2);}//arr[L...R]，后手获得的最好分数返回public static int g(int[]arr,int L,int R) {if(L==R) {return 0;}int p1= f(arr,L+1,R); //对手拿走了L位置的数的最优int p2 = f(arr,L,R-1);//对手拿走了R位置的数的最优//剩下的小的就是先手的//你获得的少，他必然获得的多，你是后手，是由对手做的决定，所以只能拿最小return Math.min(p1,p2);}

优化一（缓存法）

分析如下图可以看出有重复解：

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 ;ifor(int j =0;jfmap[i][j] = -1;gmap[i][j] = -1;}}int first = f2(arr,0,arr.length-1,fmap,gmap);int second = g2(arr,0,arr.length-1,fmap,gmap);return Math.max(first,second);}private static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {if(gmap[L][R]!=-1) {return gmap[L][R];}// 省掉一个分支，L==Rint ans = 0;if(L!=R) {int p1 = f2(arr,L+1,R,fmap,gmap);int p2 = f2(arr,L,R-1,fmap,gmap);ans = Math.min(p1,p2);}gmap[L][R] = ans;return ans;}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 = 0;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 ans;}

优化三（严格表优化）

如下数组
【7，4，16，15，1】
两张表应该如何填：


如上分别是f表和g表，首先看basecase，得到如下信息


主函数要f这张表里面0-n-1这个格子的值，g要0-n-1的位置，L>R的情况不存在

再找f表的依赖，它依赖g表的L+1和R位置，以及L和R-1位置，再找g表的依赖，g依赖于f这张表的L+1和R位置，以及L和R-1位置。

则可以根据f表的对角线去推出g的对角线，通过g的对角线推f的对角线。

 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 startCol = 1; startCol < N; startCol++) {int row = 0;int col = startCol;while (col < N) {fmap[row][col] = Math.max(arr[row] + gmap[row + 1][col],arr[col] + gmap[row][col - 1]);gmap[row][col] = Math.min(fmap[row + 1][col],fmap[row][col - 1]);row++;col++;}}return Math.max(fmap[0][N-1],gmap[0][N-1]);}