题目:62. 不同路径
思路:
首先想到的是数论方法组合数其实就是向右和向下的步数是固定的,就找一个组合的个数就可以了。
状态转移方程:一个位置的路径数就是,上面位置和左面位置路径数的和
按照动规五部曲来分析:
-
确定dp数组(dp table)以及下标的含义:
dp[i][j]:表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。
-
确定递推公式:
想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。此时在回顾一下 dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。那么很自然,dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。
-
dp数组的初始化:
如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。
所以初始化代码为:
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
-
确定遍历顺序:
这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
-
举例推导dp数组:
代码:
func uniquePaths(m int, n int) int {
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-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
参考:
题目:63. 不同路径 II
思路:
和上面差不多,多了一个检查的操作。
代码:
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
lrow, lcol := len(obstacleGrid), len(obstacleGrid[0])
//如果在起点或终点出现了障碍,直接返回0
if obstacleGrid[lrow-1][lcol-1] == 1 || obstacleGrid[0][0] == 1 {
return 0
}
// 定义一个dp数组
dp := make([][]int, lrow)
for i, _ := range dp {
dp[i] = make([]int, lcol)
}
// 初始化, 如果是障碍物, 后面的就都是0, 不用循环了
for i := 0; i < lrow && obstacleGrid[i][0] == 0; i++ {
dp[i][0] = 1
}
for i := 0; i < lcol && obstacleGrid[0][i] == 0; i++ {
dp[0][i] = 1
}
// dp数组推导过程
for i := 1; i < lrow; i++ {
for j := 1; j < lcol; j++ {
// 如果obstacleGrid[i][j]这个点是障碍物, 那么dp[i][j]保持为0
if obstacleGrid[i][j] != 1 {
// 否则我们需要计算当前点可以到达的路径数
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[lrow-1][lcol-1]
}