暴力递归到动态规划
思路
1 题目 ——> 尝试方法 ——> 暴力递归 —(可变参数)—> 记忆化搜索（dp） ——> 严格表结构（dp）
2 暴力递归到记忆化搜索，增加dp表结构，记录递归的结果，减少重复递归的计算
3 严格表结构，在记忆化搜索的dp表结果上，通过递归函数找到dp表结构内部之间的依赖关系，在不使用递归的情况下，只通过表的内部关系将dp表补充完整，找到答案对应dp表中的结果
4 严格表结构的求解顺序：（1）可变参数的确定（2）终止位置的确定（3）根据basecase确定不用计算的位置（4）观察依赖，推理内部普遍位置（5）确定依次推理的顺序
5 注意在暴力递归时每个 if 语句都是有 return 结尾的，所以都是 if 可以没有 else if 。但是在改写成动态规划后一定要确定是 if 还是 else if
6 关键点：可变参数的确定，可变参数的范围，数目是评价尝试方法的重要指标
题目一：机器人走K步到达M点问题
假设有排成一行的N个位置，记为1~N，N一定大于或等于2;
开始时机器人在M（1 <= M <= N）位置上，
如果机器人位于1位置，那么下一步只能走到2位置，
如果机器人位于N位置，那么下一步只能走到N-1位置，
如果机器人位于中间的任一位子，那么下一步可以向左走，也可以向右走。
机器人必须走K步，最终来到P（1 <= P <= N），给定参数N，M，K，P，有多少种走法？
暴力递归
- 尝试方法：运动分为向左或向右两种情况，尝试所有的移动可能，步数走完到达结束位置就算成功
public static int walkWays(int N, int M, int K, int P){ return process(N, P, K, M); } public static int process(int N, int end, int rest, int cur){ //N固定参数：开始格子的大小 //end固定参数：结束位置 //rest可变参数：剩余的步数 //cur可变参数：目前的位置 if (rest == 0){ //步数用完，停在结束位置，本次尝试正确 //basecase return cur == end ? 1 : 0; } if (cur == 1){ //1位置，下一步只能走到2 return process(N, end, rest - 1, 2); } if (cur == N){ //N位置，下一步只能走到N - 1; return process(N, end, rest - 1, N - 1); } return process(N, end, rest - 1, cur - 1) + process(N, end, rest - 1, cur + 1); }
时间复杂度：整个决策可以看成一颗二叉树，高度就是步数k，则为，O(2 ^ k)
记忆化搜索dp
- 从暴力递归到记忆化搜索dp
（1）若 1，2，3，4，5 从2开始到4结束，步数为4，N为5
（2）N，end为固定参数每次调用都相同省去，rest与cur留下
（3）暴力递归，将所有的结构都列出来，下图中：f(2，2）得到的结果一定是相同的，但是在暴力递归中会重复计算
（4）思路：利用空间记录相同的计算结果，减少计算次数，实现记忆化搜索
- 增加记录相同计算过程的缓存结构：dp
- 每次将结构记录到dp中，相同的计算不再进行递归
public static int walkWays(int N, int M, int K, int P){ //记忆化搜索 //由可变参数的范围和数量，确定dp的规模 //rest的范围 0 ~ K，cur的访问 1 ~ N，dp二维表 int[][] dp = new int[K + 1][N + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ //dp数组中的默认值为0 //将dp中所有位置的值改为负一 dp[i][j] = -1; } } return process(N, P, K, M, dp); } public static int process(int N, int end, int rest, int cur, int[][] dp){ //N固定参数：开始格子的大小 //end固定参数：结束位置 //rest可变参数：剩余的步数 //cur可变参数：目前的位置 //增加dp参数 if (dp[rest][cur] != -1){ //dp[][]不为负一，说明已经进行过计算，不用再次递归 return dp[rest][cur]; } //返回之前，都在dp[][]中记录 if (rest == 0){ //步数用完，停在结束位置，本次尝试正确 //basecase dp[rest][cur] = cur == end ? 1 : 0; return dp[rest][cur]; } if (cur == 1){ //1位置，下一步只能走到2 dp[rest][cur] = process(N, end, rest - 1, 2, dp); } else if (cur == N){ //N位置，下一步只能走到N - 1; dp[rest][cur] = process(N, end, rest - 1, N - 1, dp); } else { dp[rest][cur] = process(N, end, rest - 1, cur - 1, dp) + process(N, end, rest - 1, cur + 1, dp); } return dp[rest][cur]; }
时间复杂度：因为，递归每次都在填dp的表，且重复，所以时间复杂度由dp的规模决定，O(K * N)，
K步数，N格子的个数
严格表结构dp
- 记忆化搜索dp到严格表结构dp
（1）若 1，2，3，4，5 从2开始到4结束，步数为4，N为5
（2）由rest与cur得到dp表，* 号位置代表最终返回位置
（3）由basecase得到，rest = 0，只有cur = 2时为 1，其余均为 0，并且cur != 0
（4）通过递归函数找依赖关系：cur = 1，依赖右上角（则：cur = 1 ， rest = 1时其值与cur = 2 ，rest = 0时相同为0）cur = N，依赖左上角，其余cur，依赖左上角 + 右上角，每行开始依次补充完整dp表
（5）顺序：从左到右，从上到下
public static int walkWays(int N, int M, int K, int P){ //严格表结构 //由可变参数的范围和数量，确定dp的规模 //rest的范围 0 ~ K，cur的访问 1 ~ N，dp二维表 //dp[K][M]答案的位置，步数K，初始位置M //dp[0][P]初始值为1的位置，步数为0，结束位置为要求位置 int[][] dp = new int[K + 1][N + 1]; dp[0][P] = 1; for (int i = 1; i < dp.length; i++){ //按照行的顺序依次补充表结构 //cur为1的位置，其值依赖于其右上角 dp[i][1] = dp[i - 1][2]; for (int j = 2; j < dp[0].length - 1; j++){ //其余位置依赖于左上角 + 右上角 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; } //cur为N的位置，其值依赖于其左上角 dp[i][N] = dp[i - 1][N - 1]; } return dp[K][M]; }
题目二：零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
暴力递归
- 尝试方法：从左先右，每个硬币分为要或不要，尝试所有可能，硬币遍历结束后达到总金额就算成功
public static int minCoint(int[] coins, int amout){ //使用较少的硬币 //构造成功返回硬币个数 //构造失败返回 -1 return process(coins, amout, 0); } public static int process(int[] coins, int rest, int index){ //index目前遍历到硬币数组的位置 //rest目前还要达到的金额 if (rest < 0){ //出现负数，构成失败 return -1; } if (rest == 0){ //构造成功 return 0; } //rest > 0 if (index == coins.length){ //rest > 0时，coins数组已经用完，构造失败 return -1; } //p1不要index位置的硬币 int p1 = process(coins, rest, index + 1); //p2要index位置的硬币 int p2 = process(coins, rest - coins[index], index + 1); if (p1 == -1 && p2 == -1){ //要和不要都失败 return -1; } else { if (p1 == -1){ //不要失败，选择要，硬币数加一 return p2 + 1; } if (p2 == -1){ //要失败，选择不要 return p1; } //要不要都可以，选择使用总硬币数少的 return Math.min(p1, p2 + 1); } }
记忆化搜索dp
- 增加记录缓存结构dp
- 使用变化参数rest，index建立dp表
public static int minCoint(int[] coins, int amout){ //使用较少的硬币 //构造成功返回硬币个数 //构造失败返回 -1 int[][] dp = new int[amout + 1][coins.length + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ //因为-1，在此题中有含义，故将初始值设置为-2 dp[i][j] = -2; } } return process(coins, amout, 0, dp); } public static int process(int[] coins, int rest, int index, int[][] dp){ //动态规划 //index目前遍历到硬币数组的位置 //rest目前还要达到的金额 if (rest < 0){ //二维数组中rest不能为负数，所以放在最开始位置 return -1; } if (dp[rest][index] != -2){ return dp[rest][index]; } if (rest == 0){ //构造成功 dp[rest][index] = 0; } else if (index == coins.length){ //rest > 0时，coins数组已经用完，构造失败 dp[rest][index] = -1; } else { //p1不要index位置的硬币 int p1 = process(coins, rest, index + 1, dp); //p2要index位置的硬币 int p2 = process(coins, rest - coins[index], index + 1, dp); if (p1 == -1 && p2 == -1){ //要和不要都失败 dp[rest][index] = -1; } else { if (p1 == -1){ //不要失败，选择要，硬币数加一 dp[rest][index] = p2 + 1; }else if (p2 == -1){ //要失败，选择不要 dp[rest][index] = p1; }else { //要不要都可以，选择使用总硬币数少的 dp[rest][index] = Math.min(p1, p2 + 1); } } } return dp[rest][index]; }
严格表结构dp
- 若coins为 [2，3，5，1] , amount为6
（1）根据递归函数初始化，rest = 0，值为0，index = 4，值为 -1，求（0，6）的位置，即初始化设置 rest = 0，其值为0，初始化设置 index = coins.length，其值为 -1
（2）内部的点由上一个点的（rest, index + 1）与（rest - coins[index], index + 1）共同决定
（3）整体填表的顺序由 index 从 coins.length - 1 到 0，rest 从 1 到 amount + 1
（4）结过在dp[ amount ][ 0 ]
public static int minCoint(int[] coins, int amount) { //严格表结构 int[][] dp = new int[amount + 1][coins.length + 1]; for (int col = 0; col < coins.length + 1; col++) { //初始化设置 rest = 0，其值为0 dp[0][col] = 0; } for (int row = 1; row < amount + 1; row++) { //初始化设置 index = coins.length，其值为 -1 dp[row][coins.length] = -1; } for (int index = coins.length - 1; index >= 0; index--) { for (int rest = 1; rest < amount + 1; rest++) { //内部剩余点的设置 //将递归改为给dp表填值 //p1不要index位置的硬币 int p1 = dp[rest][index + 1]; //p2要index位置的硬币 int p2 = -1; if (rest - coins[index] >= 0){ p2 = dp[rest - coins[index]][index + 1]; } if (p1 == -1 && p2 == -1) { //要和不要都失败 dp[rest][index] = -1; } else { if (p1 == -1) { //不要失败，选择要，硬币数加一 dp[rest][index] = p2 + 1; }else if (p2 == -1) { //要失败，选择不要 dp[rest][index] = p1; }else { //要不要都可以，选择使用总硬币数少的 dp[rest][index] = Math.min(p1, p2 + 1); } } } } //返回指定位置的值 return dp[amount][0]; }
题目三：拿纸牌比最大问题
暴力递归
- 思路：
（1）分为两种拿牌方式，先手和后手，若范围为left ~ right
（2）先手分为左右，若拿left，值就是就是left位置的值 + 后手的值(left + 1 ~ right后手)；若拿right，值就是right位置的值 + 后手的值(left ~ right - 1后手)，返回二者值中较大的
（3）后手分为对手拿左还是右，若对手拿left，值就是先手的值(left + 1 ~ right先手)；若拿right，值就是先手的值(left ~ right - 1先手)，因为对手一定拿最优解，那么后手一定是二者值中较小的情况
（4）若 left == right 先手就是 left位置的值，后手就是0
public static int win(int[] arr){ if (arr == null || arr.length == 0){ return 0; } int valueA = first(arr, 0, arr.length - 1); //A的先手情况 int valueB = second(arr, 0, arr.length - 1); //B的后手情况 return Math.max(valueA, valueB); } public static int first(int[] arr, int left, int right){ //先手获得的最好分数 if (left == right){ //递归结束条件 return arr[left]; } int l = arr[left] + second(arr, left + 1, right); //拿左边 int r = arr[right] + second(arr, left, right - 1); //拿右边 return Math.max(l, r); } public static int second(int[] arr, int left, int right){ //先手获得的最好分数 if (left == right){ //递归结束条件 return 0; } int l = first(arr, left + 1, right); //对手拿走了左边 int r = first(arr, left, right - 1); //对手拿走了右边 //因为对手一定会挑选最优情况，所以留给后手一定是俩者中较差的选择 return Math.min(l, r); }
记忆化搜索dp
- 有两个递归函数，构建两个dp表进行记录
public static int win(int[] arr){ if (arr == null || arr.length == 0){ return 0; } int[][] dpF = new int[arr.length][arr.length]; int[][] dpS = new int[arr.length][arr.length]; for (int i = 0; i < dpF.length; i++){ for (int j = 0; j < dpF[0].length; j++){ //初始化，为填入时全为 -1 dpF[i][j] = -1; dpS[i][j] = -1; } } int valueA = first(arr, 0, arr.length - 1, dpF, dpS); //A的先手情况 int valueB = second(arr, 0, arr.length - 1, dpF, dpS); //B的后手情况 return Math.max(valueA, valueB); } public static int first(int[] arr, int left, int right, int[][] dpF, int[][] dpS){ //先手获得的最好分数 //在first递归函数中加入 dpF缓存 if (dpF[left][right] != - 1){ return dpF[left][right]; } if (left == right){ //递归结束条件 dpF[left][right] = arr[left]; } else { int l = arr[left] + second(arr, left + 1, right, dpF, dpS); //拿左边 int r = arr[right] + second(arr, left, right - 1, dpF, dpS); //拿右边 dpF[left][right] = Math.max(l, r); } return dpF[left][right]; } public static int second(int[] arr, int left, int right, int[][] dpF, int[][] dpS){ //先手获得的最好分数 //在second递归函数中加入 dpS缓存 if (dpS[left][right] != - 1){ return dpS[left][right]; } if (left == right){ //递归结束条件 dpS[left][right] = 0; } else { int l = first(arr, left + 1, right, dpF, dpS); //对手拿走了左边 int r = first(arr, left, right - 1, dpF, dpS); //对手拿走了右边 dpS[left][right] = Math.min(l, r); } //因为对手一定会挑选最优情况，所以留给后手一定是俩者中较差的选择 return dpS[left][right]; }
严格表结构
例：arr[] = [3，100，4，50]
（1）first dp表与 second dp表中 因为 left 始终在 right 左侧 所以都只有上半侧，* 号为目标位置
（2）初始化当 left == right：first 中为 arr[ left ]，second 中为 0
（3）普遍位置的依赖关系：first 与 second 分别互相依赖；例：first(0, 3) 由 second(1, 3) 与 second(0, 2)共同决定
（4）次序：依次求对角线，整体从上往下，从左往右，最终位置 [0][arr.length - 1]
public static int win(int[] arr){ if (arr == null || arr.length == 0){ return 0; } int[][] dpF = new int[arr.length][arr.length]; int[][] dpS = new int[arr.length][arr.length]; for (int i = 0; i < dpF.length; i++){ //初始化 dpF[i][i] = arr[i]; dpS[i][i] = 0; } for (int n = 1; n < arr.length; n++){ //斜对角线的添加 int col = n; for (int row = 0; row < arr.length - n; row++){ dpF[row][col] = Math.max(arr[col] + dpS[row][col - 1], arr[row] + dpS[row + 1][col]); dpS[row][col] = Math.min(dpF[row][col - 1], dpF[row + 1][col]); col++; } } return Math.max(dpF[0][arr.length - 1], dpS[0][arr.length - 1]); }
题目四：象棋问题（三维动态规划）
- 问题描述：
给你一个棋盘，长为10，宽为9，然后在棋盘的[0,0]位置，有一个马，马走日嘛，就是象棋的规则，现在在棋盘上给你一个位置[a,b]，给你k步，请你求出，马走到【a，b】位置并且走k步，可以有多少种走法？
暴力递归
- 尝试方法：所有马可能的落点进行尝试，可以改写成从[a, b] 到 [0, 0]用k步，basecase为 k = 0
public static int getWays(int a, int b, int k){ return process(a, b, k); } public static int process(int x, int y, int step){ //x，y目前位置的坐标 //step还剩的步数 if (x < 0 || x > 8 || y < 0 || y > 9){ //出界情况 return 0; } if (step == 0){ //basecase return x == 0 && y == 0 ? 1 : 0; } return process(x - 1, y + 2, step - 1) + process(x + 1, y + 2, step - 1) + process(x - 1, y - 2, step - 1) + process(x + 1, y - 2, step - 1) + process(x - 2, y + 1, step - 1) + process(x + 2, y + 1, step - 1) + process(x - 2, y - 1, step - 1) + process(x + 2, y - 1, step - 1); }
记忆化搜索dp
- 三维表结构记录
public static int getWays(int a, int b, int k){ int[][][] dp = new int[9][10][k + 1]; for (int x = 0; x < dp.length; x++){ for (int y = 0; y < dp[0].length; y++){ for (int z = 0; z < dp[0][0].length; z++){ dp[x][y][z] = -1; } } } return process(a, b, k, dp); } public static int process(int x, int y, int step, int[][][] dp){ //x，y目前位置的坐标 //step还剩的步数 if (x < 0 || x > 8 || y < 0 || y > 9){ //出界情况 return 0; } if (dp[x][y][step] != - 1){ return dp[x][y][step]; } if (step == 0){ //basecase dp[x][y][step] = x == 0 && y == 0 ? 1 : 0; } else{ dp[x][y][step] = process(x - 1, y + 2, step - 1, dp) + process(x + 1, y + 2, step - 1, dp) + process(x - 1, y - 2, step - 1, dp) + process(x + 1, y - 2, step - 1, dp) + process(x - 2, y + 1, step - 1, dp) + process(x + 2, y + 1, step - 1, dp) + process(x - 2, y - 1, step - 1, dp) + process(x + 2, y - 1, step - 1, dp); } return dp[x][y][step]; }
严格表结构dp
（1）初始化：最底层（0，0，0）位置是1，其余（x，y，0）位置均为0
（2）每一次都根据其下一层得到
（3）一层一层填写，x，y的顺序不影响，最终位置为（x，y，step）
public static int getWays(int x, int y, int step){ if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0){ //出界情况 return 0; } int[][][] dp = new int[9][10][step + 1]; //初始化 dp[0][0][0] = 1; for (int z = 1; z < dp[0][0].length; z ++){ //一次一次的填充 for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ dp[i][j][z] += process(i - 1, j + 2, z - 1, dp); dp[i][j][z] += process(i + 1, j + 2, z - 1, dp); dp[i][j][z] += process(i - 1, j - 2, z - 1, dp); dp[i][j][z] += process(i + 1, j - 2, z - 1, dp); dp[i][j][z] += process(i - 2, j + 1, z - 1, dp); dp[i][j][z] += process(i + 2, j + 1, z - 1, dp); dp[i][j][z] += process(i - 2, j - 1, z - 1, dp); dp[i][j][z] += process(i + 2, j - 1, z - 1, dp); } } } return dp[x][y][step]; } public static int process(int x, int y, int step, int[][][] dp){ //防止越界 if (x < 0 || x > 8 || y < 0 || y > 9){ //出界情况 return 0; } return dp[x][y][step]; }
