题目：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]
}