👉不同路径👈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
思路：
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> pathNum(m, vector<int>(n, 1)); // 已经设置好初始状态了 for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { pathNum[i][j] = pathNum[i - 1][j] + pathNum[i][j - 1]; } } return pathNum[m - 1][n - 1]; } };
👉不同路径II👈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
思路：
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) { return 0; } vector<vector<int>> path(m, vector<int>(n, 0)); // 初始状态 for(int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) path[i][0] = 1; for(int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) path[0][j] = 1; for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { if(obstacleGrid[i][j]) // 点(i, j)有障碍，无法到达该点，故path[i][j] = 0 { continue; } else { path[i][j] = path[i-1][j] + path[i][j-1]; } } } return path[m-1][n-1]; } };
👉最小路径和👈
给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。注意：你每次只能向下或向右移动。
示例一：
输入：[[1,2],[5,6],[1,1]]
返回值：8
思路：
class Solution { public: int minPathSum(vector<vector<int> >& grid) { if(grid.size() == 0) { return 0; } int m = grid.size(); int n = grid[0].size(); // 初始状态 for(int i = 1; i < m; ++i) grid[i][0] += grid[i - 1][0]; for(int j = 1; j < n; ++j) grid[0][j] += grid[0][j - 1]; for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; } };
👉总结👈
本篇博客主要讲解了路径总数和最小路径和，问题的状态和状态转移方程都比较好写出来，难度较低。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
