算法——路径问题

路径总数

题目描述：

  在一个m*n的网格的左上角有一个机器人，机器人在任何时候只能向下或者向右移动，机器人试图到达网格的右下角，有多少可能的路径。

来源：牛客链接

思路：动态规划

F(i,j) = F(i-1,j) + F(i,j-1) 特殊情况：第0行和第0列  F(0,i) = 1  F(i,0) = 1

代码：

import java.util.*; public class Solution { /** * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths(int m, int n) { // write code here List<List<Integer>> pathNum = new ArrayList<>(); // 申请F(i,j)空间，初始化 for (int i = 0; i < m; ++i) { pathNum.add(new ArrayList<>()); pathNum.get(i).add(1); } for (int i = 1; i < n; ++i) { pathNum.get(0).add(1); } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { // F(i,j) = F(i-1,j) + F(i,j-1) pathNum.get(i).add(pathNum.get(i).get(j - 1) + pathNum.get(i - 1).get(j)); } } return pathNum.get(m - 1).get(n - 1); } }

路径总数（有障碍物）

题目描述：

继续求路径。 如果在图中加入了一些障碍，有多少不同的路径？ 分别用0和1代表空区域和障碍

来源：牛客链接

思路：动态规划

F(i,j) = {F(i-1,j) + F(i,j-1)} OR {0, if obstacleGrid(i,j) = 1} 特殊情况：第0行和第0列   F(0,i) = {1} OR {0, if obstacleGrid(0,j) = 1, j <= i}   F(i,0) = {1} OR {0, if obstacleGrid(j,0) = 1, j <= i}

代码：

package java_1004; import java.util.*; public class Solution { /** * * @param obstacleGrid int整型二维数组 * @return int整型 */ public int uniquePathsWithObstacles (int[][] obstacleGrid) { // write code here if(obstacleGrid==null)return 0; List<List<Integer>> pathNum = new ArrayList<>(); int m = obstacleGrid.length; int n = obstacleGrid[0].length; // 申请F(i,j)空间，初始化 // 初始化第0列 for (int i = 0; i < m; ++i) { pathNum.add(new ArrayList<>()); //如果当前位置有障碍，则无法到达 if (obstacleGrid[i][0] == 1) pathNum.get(i).add(0); else { //如果当前位置无障碍，但是前面如果到达不了，当前位置也达到不了 if (i > 0) { if (pathNum.get(i - 1).get(0) == 1) pathNum.get(i).add(1); else pathNum.get(i).add(0); } else pathNum.get(i).add(1); } } //初始化第一行 for (int i = 1; i < n; ++i) { if (obstacleGrid[0][i] == 1) pathNum.get(0).add(0); else { if (pathNum.get(0).get(i - 1) == 1) pathNum.get(0).add(1); else pathNum.get(0).add(0); } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { // obstacleGrid[i][j] = 1 时，F(i,j)无法到达 if (obstacleGrid[i][j] == 1) pathNum.get(i).add(0); else // F(i,j) = F(i-1,j) + F(i,j-1) pathNum.get(i).add(pathNum.get(i).get(j - 1) + pathNum.get(i - 1).get(j)); } } return pathNum.get(m - 1).get(n - 1); } }

最小路径和（左上角到右下角）

题目描述

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。 注意：你每次只能向下或向右移动。

来源：牛客链接

思路：动态规划

F(i,j) = min{F(i-1,j) , F(i,j-1)} + F(i,j) 特殊情况：第0行和第0列   F(0,i) = F(0,i-1) + (0,i)   F(i,0) = F(i-1,0) + (i,0)

代码：

import java.util.*; public class Solution { /** * * @param grid int整型二维数组 * @return int整型 */ public int minPathSum (int[][] grid) { // write code here int row = grid.length; int col = grid[0].length; // 如果为空或者只有一行，返回0 if(row == 0 || col == 0) { return 0; } // F(0,0), F(0,i), F(i,0)初始化 for(int i = 1;i < row;i++) { grid[i][0] = grid[i - 1][0] + grid[i][0]; } for(int i = 1;i < col;i++) { grid[0][i] = grid[0][i - 1] + grid[0][i]; } // F(i,j) = min{F(i-1,j) , F(i,j-1)} + F(i,j) for(int i=1;i < row;i++){ for(int j = 1;j < col;j++) { grid[i][j] = Math.min(grid[i - 1][j],grid[i][j - 1]) + grid[i][j]; } } return grid[row-1][col-1]; } }