代码随想录补打卡 62不同路径 63 不同路径2
代码如下
func uniquePaths(m int, n int) int {
dp := make([][]int,m) //定义一个二维数组
for i := 0 ; i < m ; i++ { //遍历这个二维数组的每个元素，并将每个元素都定义为一个一维数组
dp[i] = make([]int,n) //这样就生成了图中的一个二维网格
dp[i][0] = 1 //并且将第一列的每个元素的值赋为1 i代表元素的横坐标j代表纵坐标
}
for j := 0 ; j < n ; j++ { //将第一行赋值
dp[0][j] = 1
}
for i := 1 ; i < m ; i++ { 遍历整个数组，从1,1开始
for j := 1 ; j < n ; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
不同路径2
代码如下
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m := len(obstacleGrid) //二维数组的行数为障碍物的元素个数
n := len(obstacleGrid[0]) //二维数组的列数为障碍物每个元素里的个数，即一维数组元素的个数
dp := make([][]int,m) // 和之前不同路径的思路一样，构造二维数组的网格
for i := 0 ; i < m ; i++ {
dp[i] = make([]int,n)
}
for i := 0 ; i < m && obstacleGrid[i][0] == 0 ; i++ { //对第一列和第一行进行初始化的时候，如果出现障碍物，则之后的元素不需要初始化
dp[i][0] = 1
}
for j := 0 ; j < n && obstacleGrid[0][j] == 0 ; j++ {
dp[0][j] = 1
}
for i := 1 ; i < m ; i++ {
for j := 1 ; j < n ; j++ {
if obstacleGrid[i][j] != 1 { //如果没有障碍，则可以进行计算，如果有障碍，那么这一个障碍物的点的值仍为0
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1]
}