小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录5.不同路径题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析6.不同路径II题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语5.不同路径题目链接62. 不同路径 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式i.从[ij]位置出发巴拉巴拉ii.从起始位置出发到达[ij]位置巴拉巴拉。这里选择第二种定义状态表示的方式dp[ i ][ j ]表示走到[ij]位置处一共有多少种方式。2.状态转移方程简单分析一下。如果dp[ i ][ j ]表示到达[ij]位置的方法数那么到达[ij]位置之前的一小步有两种情况i.从[[ij]位置的上方([i - 1j]的位置)向下走一步转移到[ij]位置;ii.从[ij]位置的左方([ij-1]的位置)向右走一步转移到[ij]位置。由于我们要求的是有多少种方法因此状态转移方程就呼之欲出了dp[ i ][ j ]dp[ i - 1 ][ j ] dp[ i ][ j - 1 ]。3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i辅助结点里面的值要「保证后续填表是正确的」;ii.「下标的映射关系」。在本题中「添加一行」并且「添加一列」后只需将dp[0][1]的位置初始化为1即可。4.填表顺序根据「状态转移方程」的推导来看填表的顺序就是「从上往下」填每一行在填写每一行的时候「从左往右」。5.返回值根据「状态表示」我们要返回dp[ m ][ n ]的值。C算法代码class Solution { public: int uniquePaths(int m, int n) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 vectorvectorint dp(m 1, vectorint(n 1)); 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]; } };算法总结及流程解析6.不同路径II题目链接63. 不同路径 II - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路这道题算法逻辑和上面一题基本是十分类似的唯一不同的在于状态转移方程需要考虑有无障碍的情况状态转移方程简单分析一下。如果dp[i][j]表示到达[ij]位置的方法数那么到达[ij]位置之前的一小步有两种情况i.从[ij]位置的上方([i -1j]的位置)向下走一步转移到[ij]位置;ii.从[ij]位置的左方([ij- 1]的位置)向右走一步转移到[ij]位置。但是[i- 1j]与[ij- 1]位置都是可能有障碍的此时从上面或者左边是不可能到达[ij]位置的也就是说此时的方法数应该是0。由此我们可以得出一个结论只要这个位置上「有障碍物」那么我们就不需要计算这个位置上的值直接让它等于0即可。C算法代码class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m obstacleGrid.size(); int n obstacleGrid[0].size(); vectorvectorint dp(m 1, vectorint(n 1)); dp[0][1] 1; for(int i 1; i m; i) { for(int j 1; j n; j) { if(obstacleGrid[i - 1][j - 1] 0)//一定要注意dp数组和题目数组的映射关系 { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } } return dp[m][n]; } };算法总结及流程解析结束语到此5.不同路径6.不同路径II 这两道算法题就讲解完了。不同路径通过状态表示dp[i][j]记录到达(i,j)的路径数状态转移方程为dp[i][j]dp[i-1][j]dp[i][j-1]并采用辅助结点技巧初始化。不同路径II在第一题基础上增加了障碍物判断遇到障碍物时路径数置0。希望大家能有所收获
《算法题讲解指南：动态规划算法--路径问题》--5.不同路径，6.不同路径II
小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录5.不同路径题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析6.不同路径II题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语5.不同路径题目链接62. 不同路径 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式i.从[ij]位置出发巴拉巴拉ii.从起始位置出发到达[ij]位置巴拉巴拉。这里选择第二种定义状态表示的方式dp[ i ][ j ]表示走到[ij]位置处一共有多少种方式。2.状态转移方程简单分析一下。如果dp[ i ][ j ]表示到达[ij]位置的方法数那么到达[ij]位置之前的一小步有两种情况i.从[[ij]位置的上方([i - 1j]的位置)向下走一步转移到[ij]位置;ii.从[ij]位置的左方([ij-1]的位置)向右走一步转移到[ij]位置。由于我们要求的是有多少种方法因此状态转移方程就呼之欲出了dp[ i ][ j ]dp[ i - 1 ][ j ] dp[ i ][ j - 1 ]。3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i辅助结点里面的值要「保证后续填表是正确的」;ii.「下标的映射关系」。在本题中「添加一行」并且「添加一列」后只需将dp[0][1]的位置初始化为1即可。4.填表顺序根据「状态转移方程」的推导来看填表的顺序就是「从上往下」填每一行在填写每一行的时候「从左往右」。5.返回值根据「状态表示」我们要返回dp[ m ][ n ]的值。C算法代码class Solution { public: int uniquePaths(int m, int n) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 vectorvectorint dp(m 1, vectorint(n 1)); 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]; } };算法总结及流程解析6.不同路径II题目链接63. 不同路径 II - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路这道题算法逻辑和上面一题基本是十分类似的唯一不同的在于状态转移方程需要考虑有无障碍的情况状态转移方程简单分析一下。如果dp[i][j]表示到达[ij]位置的方法数那么到达[ij]位置之前的一小步有两种情况i.从[ij]位置的上方([i -1j]的位置)向下走一步转移到[ij]位置;ii.从[ij]位置的左方([ij- 1]的位置)向右走一步转移到[ij]位置。但是[i- 1j]与[ij- 1]位置都是可能有障碍的此时从上面或者左边是不可能到达[ij]位置的也就是说此时的方法数应该是0。由此我们可以得出一个结论只要这个位置上「有障碍物」那么我们就不需要计算这个位置上的值直接让它等于0即可。C算法代码class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m obstacleGrid.size(); int n obstacleGrid[0].size(); vectorvectorint dp(m 1, vectorint(n 1)); dp[0][1] 1; for(int i 1; i m; i) { for(int j 1; j n; j) { if(obstacleGrid[i - 1][j - 1] 0)//一定要注意dp数组和题目数组的映射关系 { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } } return dp[m][n]; } };算法总结及流程解析结束语到此5.不同路径6.不同路径II 这两道算法题就讲解完了。不同路径通过状态表示dp[i][j]记录到达(i,j)的路径数状态转移方程为dp[i][j]dp[i-1][j]dp[i][j-1]并采用辅助结点技巧初始化。不同路径II在第一题基础上增加了障碍物判断遇到障碍物时路径数置0。希望大家能有所收获
