dp
1、62. 不同路径
题目：
求路径方案多少个
思路：
- 这道题就有点dp了哈
func uniquePaths(m int, n int) int {
//dp，写过,代表的是多少种
// 初始化
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
dp[i][0] = 1 // 代表到这里只有一种路径
}
for j := 0; j<n; j++ {
dp[0][j] = 1
}
for i:=1; i<m; i++ {
for j:=1; j<n; j++ {
dp[i][j] = dp[i][j-1]+dp[i-1][j]
}
}
return dp[m-1][n-1]
}
2、63. 不同路径 II
题目：
思路：
- 简单
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
// 还是写过了,和1很像，考虑一下障碍物即可
m,n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
for i:=0; i<m&&obstacleGrid[i][0] != 1; i++ {
dp[i][0] = 1
}
for j:=0; j<n&&obstacleGrid[0][j] != 1; j++ {
dp[0][j] = 1
}
for i:=1; i<m; i++ {
for j:=1; j<n; j++ {
if obstacleGrid[i][j] != 1 {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1]
}
