leetcode 62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
示例 1:输入: m = 3, n = 2 输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:输入: m = 7, n = 3 输出: 28
如果申请一个二维空间的dp[][],那么状态转移方程为dp[i][j] = dp[i - 1][j]+dp[i][j - 1];
public int uniquePaths1(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
//空间压缩
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}
int[] dp = new int[n];
dp[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
} leetcode 63. 不同路径 II
/**
* 空间压缩
* @param obstacleGrid
* @return
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) {
return 0;
}
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
return 0;
}
int[] dp = new int[col];
dp[0] = 1;
for (int i = 1; i < col; i++) {
if (dp[i - 1] == 0 || obstacleGrid[0][i] == 1) {
dp[i] = 0;
} else {
dp[i] = 1;
}
}
for (int i = 1; i < row; i++) {
if (dp[0] == 1 && obstacleGrid[i][0] == 0) {
dp[0] = 1;
}else {
dp[0] = 0;
}
for (int j = 1; j < col; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else {
dp[j] = dp[j - 1] + dp[j];
}
}
}
return dp[col - 1];
}
public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) {
return 0;
}
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
if (obstacleGrid[0][0] == 1 || obstacleGrid[row - 1][col - 1] == 1) {
return 0;
}
int[][] dp = new int[row][col];
dp[0][0] = 1;
for (int i = 1; i < row; i++) {
if (dp[i - 1][0] == 0 || obstacleGrid[i][0] == 1) {
dp[i][0] = 0;
} else {
dp[i][0] = 1;
}
}
for (int i = 1; i < col; i++) {
if (dp[0][i - 1] == 0 || obstacleGrid[0][i] == 1) {
dp[0][i] = 0;
} else {
dp[0][i] = 1;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[row - 1][col - 1];
} leetcode 64. 最小路径和
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
for (int i = 1; i < row; i++) {
dp[i][0] = grid[i][0] + dp[i - 1][0];
}
for (int i = 1; i < col; i++) {
dp[0][i] = grid[0][i] + dp[0][i - 1];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[row - 1][col - 1];
}
//空间压缩
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int[] dp = new int[col];
//初始化第一行
dp[0] = grid[0][0];
for (int i = 1; i < col; i++) {
dp[i] = dp[i - 1] + grid[0][i];
}
for (int i = 1; i < row; i++) {
dp[0] = grid[i][0] + dp[0];
for (int j = 1; j < col; j++) {
dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
}
}
return dp[col - 1];
} 动态规划，说白了就是用缓存来记录一些重复子问题，避免重复计算，是一种用空间换时间的操作。
最长递增子路径
public class LongestIncreasingPath329 {
public static void main(String[] args) {
int[][] matrix = {
{9, 9, 4},
{6, 6, 8},
{2, 1, 1}
};
int max = new LongestIncreasingPath329().longestIncreasingPath(matrix);
System.out.println(max);
}
int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
//先来看看暴力解法
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int row = matrix.length;
int col = matrix[0].length;
int path = 0;
//从每个位置出发都尝试一遍
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
path = path(matrix, i, j);
max = max > path ? max : path;
}
}
return max;
}
private int path(int[][] matrix, int row, int col) {
int num = 0;
for (int i = 0; i < 4; i++) {
int newRow = row + d[i][0];
int newCol = col + d[i][1];
if (newRow >= 0 && newCol >= 0 && newRow < matrix.length && newCol < matrix[0].length && matrix[row][col] > matrix[newRow][newCol]) {
num = num > (path(matrix, newRow, newCol)) ? num : (path(matrix, newRow, newCol));
}
}
return ++num;
}
//从中可以看出，在计算中进行了大量的重复计算，因此。可以想办法将重叠子问题记录下来，避免重复计算。
//引入一个二元数组dp[][]，用来记录从某个点出发的最长路径，也就是动态规划解法。
public int longestIncreasingPathdp(int[][] matrix) {
if(matrix == null || matrix.length == 0){
return 0;
}
int max = -1;
int row = matrix.length;
int col = matrix[0].length;
int path = 0;
int[][] dp = new int[row][col];
//从每个位置出发都尝试一遍
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
path = path(matrix, i, j,dp);
max = max > path ? max : path;
}
}
return max;
}
private int path(int[][] matrix, int row, int col,int[][] dp) {
if(dp[row][col]!=0){
return dp[row][col];
}
for (int i = 0; i < 4; i++) {
int newRow = row + d[i][0];
int newCol = col + d[i][1];
if (newRow >= 0 && newCol >= 0 && newRow < matrix.length && newCol < matrix[0].length && matrix[row][col] > matrix[newRow][newCol]) {
dp[row][col] = dp[row][col] > (path(matrix, newRow, newCol,dp)) ? dp[row][col] : (path(matrix, newRow, newCol,dp));
}
}
return ++dp[row][col];
}
}
京公网安备 11010502036488号