本文主要是介绍【算法挨揍日记】day19——62. 不同路径、63. 不同路径 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
62. 不同路径
62. 不同路径
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
解题思路：
状态表示：dp[i][j]表示在到达（i，j）位置后，路线的总数
状态转移方程：
dp[i][j]=dp[i-1][j]+dp[i][j-1];
初始化：
因为我们从（1,1位置开始遍历，我们要保证1,1位置的值要为1），因此我们需要将（0,1）位置设为1，来满足状态转移方程
填表顺序：左到右
返回值：dp【m】【n】
解题代码：
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>>dp(m+1,vector<int>(n+1,0));dp[0][1]=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][n];}
};63. 不同路径 II
63. 不同路径 II
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
解题思路：
状态表示： dp[i][j]在到达（i，j）后，路线的总数
状态转移方程：当ob（i-1，j-1）等于0的时候，如果向下向右的可以的话，ob（i-1，j-1）就为0，为1的话就没有意义了
初始化：
dp【0】【1】=1
填表顺序：从左到右
返回值：dp【m】【n】；
解题代码：
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int len1=obstacleGrid.size();int len2=obstacleGrid[0].size();vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));dp[0][1]=1;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(obstacleGrid[i-1][j-1]==0)dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[len1][len2];}
};这篇关于【算法挨揍日记】day19——62. 不同路径、63. 不同路径 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
