不同路径 II
- leetcode63. 不同路径 II
- 题目描述
- 暴力递归
- 代码演示
- 动态规划
- 代码演示
- 动态规划空间压缩
- 动态规划专题
leetcode63. 不同路径 II
题目描述
暴力递归
代码演示
/**
* 主方法
*/public int uniquePathsWithObstacles(int[][] obstacleGrid) {//如果右下角是障碍物,怎么都过不去,直接返回0if(obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1){return 0;}//开始递归return process(obstacleGrid,0,0);}/*** 暴力递归* i 和 j 描述当前在的位置*/public int process(int[][]obstacleGrid,int i,int j){//base case 来到最后一个位置,前面路线有效,返回1if(i == obstacleGrid.length - 1 && j == obstacleGrid[0].length - 1 ){return 1;}//越界,路线无效 返回0if(i >= obstacleGrid.length || j >= obstacleGrid[0].length){return 0;}// 碰到障碍物,无效返回0if(obstacleGrid[i][j] == 1){return 0;}//x向下和向右两种情况int down = process(obstacleGrid,i + 1,j);int right = process(obstacleGrid,i,j + 1);//两种情况累加就是所有的路线return down + right;}
动态规划
代码演示
/*** 动态规划* @param obstacleGrid* @return*/public int uniquePathsWithObstacles(int[][] obstacleGrid) {int n = obstacleGrid.length;int m = obstacleGrid[0].length;//最有下角如果是障碍物,就无法过去,返回 0if (obstacleGrid[n - 1][m - 1] == 1) {return 0;}//动态规划表int[][]dp = new int[n][m];//来标记最后一行最后一次出现障碍物的位置int flagN = -1;//来标记最后一列最后一次出现障碍物的位置int flagM = -1;for (int i = m - 1; i >= 0;i--){if(obstacleGrid[n - 1][i] == 1){flagN = i;break;}}//最后一个障碍物之后的位置初始化为1for (int i = flagN + 1; i < m;i++){dp[n - 1][i] = 1;}//标记最后一列最后一次出现障碍物的位置.for (int j = n - 1; j >= 0;j--){if(obstacleGrid[j][m - 1] == 1){flagM = j;break;}}//最后一个障碍物之后的位置初始化为1for (int j = flagM + 1; j < n;j++){dp[j][m - 1] = 1;}for (int i = n - 2;i >= 0;i--){for (int j = m - 2;j >= 0;j--){//当前位置本身是障碍物 即为0if(obstacleGrid[i][j] == 1){dp[i][j] = 0;}else{//z状态转移方程dp[i][j] = dp[i + 1][j] + dp[i][j + 1];}}}return dp[0][0];}
动态规划空间压缩
/*** 动态规划 + 空间压缩* @param obstacleGrid* @return*/public int uniquePathsWithObstacles2(int[][] obstacleGrid) {int n = obstacleGrid.length;int m = obstacleGrid[0].length;if (obstacleGrid[n - 1][m - 1] == 1) {return 0;}int[]dp = new int[m];int flagN = -1;for (int i = m - 1; i >= 0;i--){if(obstacleGrid[n - 1][i] == 1){flagN = i;break;}}for (int i = flagN + 1; i < m;i++){dp[i] = 1;}int flagM = -1;for (int j = n - 1; j >= 0;j--){if(obstacleGrid[j][m - 1] == 1){flagM = j;break;}}for (int i = n - 2;i >= 0;i--){dp[m - 1] = i > flagM ? 1 : 0;for (int j = m - 2;j >= 0;j--){if(obstacleGrid[i][j] == 1){dp[j] = 0;}else{dp[j] = dp[j] + dp[j + 1];}}}return dp[0];}
动态规划专题
leetcode62. 不同路径
leetcode877. 石子游戏
leetcode64. 最小路径和
leetcode416. 分割等和子集
leetcode354. 俄罗斯套娃信封问题
leetcode300. 最长递增子序列
leetcode337. 打家劫舍 III
本文链接：https://my.lmcjl.com/post/13970.html
展开阅读全文
4 评论