师范街网站建设,项目开发的五个阶段,建设小说网站,网络营销推广方法总结写代码的第二十九天 继续动归#xff01;#xff01;#xff01;
62.不同路径
思路
解决问题1#xff1a;dp[i][j]的的含义是什么#xff1f;本题给的是一个二维的表#xff0c;判断从左上角走到右下角有多少种路径#xff0c;所以dp应该是二维数组#xff0c;dp[i]…写代码的第二十九天 继续动归
62.不同路径
思路
解决问题1dp[i][j]的的含义是什么本题给的是一个二维的表判断从左上角走到右下角有多少种路径所以dp应该是二维数组dp[i][j]代表的是从起始点开始走到ij位置时的路径数量。 解决问题2递推公式是什么也就是dp[i][j]本题中只能向右向下走所以ij位置的值只能由其上方或者左侧的dp值决定也就是i-1j和ij-1两个位置的值决定。dp[i-1][j]代表ij位置上方的路径数量dp[i][j-1]代表 ij位置左侧的路径数量所以dp[i][j]dp[i-1][j]dp[i][j-1]。 解决问题3dp数组如何初始化最开始的想法就是只对初始位置进行初始化但是我们根据递推公式可以看见如果我们想要第i位的值就需要i-1位的值如果i1那么就需要i0时的值也就是第一行的全部值所以初始化第一行也就是i0这一行的所有值同理也需要初始化j0这一行的全部值。dp[0][j] 1,dp[i][0]1,为什么初始化为1是因为在第一行中他只能向下走只有一条路径同理第一列中只能向右走只有一条路径所以初始化为1. 解决问题4如何确定遍历顺序我们是从左上到右下的路径所以从左到右从上到下进行遍历。 解决问题5输出搭配数组。为了判断是否和题意一致方便后续改错。 正确代码这个题中对我难度最大的是dp数组的初始化笑死没想过该怎么初始化。最后需要注意输出的是dp[m-1][n-1]因为下标是从0开始的。第一行第一列已经处理完了所以下面的range范围都是从1开始的。
class Solution:def uniquePaths(self, m: int, n: int) - int:dp [[0 for _ in range(n)] for _ in range(m)]for i in range(m):dp[i][0] 1for j in range(n):dp[0][j] 1for i in range(1,m):for j in range(1,n):dp[i][j] dp[i-1][j] dp[i][j-1]return dp[m-1][n-1]63. 不同路径 II
思路
这个题和上一个题的区别在于在这个m*n的矩阵中是有障碍物的也就是说遇到了障碍要直接越过根据已经给出了二维数组不是0的就是障碍物如果障碍在第一行那么遇到了障碍物之后的点都不能走了因为只能向右向下右侧遇到障碍物了只能向下走在向右走不能向上走所以当第一行有障碍物的时候后面所有的点不会再走过同理当第一列有障碍物的时候只能向右走在向下也就是当前障碍物下面的点都不会再走过。 根据上面的分析可以知道本题的代码和上面题的代码区别在于初始化第一行和第一列的dp数组遇到障碍之前的都是1从障碍开始的值都是零。如果在内部发现了障碍那么当前这个障碍的点dp[i][j]就不应该存储任何数值此路不通所以应该将dp[i][j]赋值为0. 正确代码m代表行n代表列
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:m len(obstacleGrid)n len(obstacleGrid[0])dp [[0 for _ in range(n)] for _ in range(m)]for i in range(m):if obstacleGrid[i][0] 0:dp[i][0] 1else:breakfor j in range(n):if obstacleGrid[0][j] 0:dp[0][j] 1else:breakfor i in range(1,m):for j in range(1,n):if obstacleGrid[i][j] 1:dp[i][j] 0else:dp[i][j] dp[i-1][j] dp[i][j-1]return dp[m-1][n-1]
