经典dp--不同路径系列之Go写法

uniquePaths[uniquePaths II](https://leetcode.com/problems/unique-paths-ii/submissions/)

uniquePaths

这是一个dp问题，最重要的是需要找到一个状态转移方程。从题目可见，机器人只能向右或者向左走，因此对于到达某一个节点，其主要有两条路径可以到达，也就是说从上面的节点以及左边的节点过来。

而假定我们有一个dp二维数组，大小为m x n, 然后存储的值是到达这个节点的路径数目，根据上面所述，我们有状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

特别地，这里可以使用优化空间版本的dp数组，也就是一个大小为n的一位数组，从左到右更新dp数组，dp[i-1]就是左边的节点，而dp[i]在未更新的情况下实际是存储上一行节点的路径信息，也就是说dp[i]就是存储上面节点的路径信息，因此有转移方程：

dp[i] = dp[i-1] + dp[i] // accept code func uniquePaths(m int, n int) int { dp := make([]int,n) for i:=0; i<n;i++ { dp[i] = 1 } for i:=1; i < m; i++ { for j:=1; j<n;j++{ dp[j] = dp[j] + dp[j-1] } // fmt.Println(dp) } return dp[n-1] }

uniquePaths II

类似I的代码创建一个数组来存储之前的路径，但是需要注意的是：

初始化的时候，当碰到obstacle后，后面所有的dp值就不用再设置了，直接利用其初始化值0在进行dp更新时，碰上obstacle该dp[i]需要置为0,特别地，每一次都要对dp[0]进行检查。 // accept code func uniquePathsWithObstacles(obstacleGrid [][]int) int { m := len(obstacleGrid) n := len(obstacleGrid[0]) dp := make([]int, n) for i:=0;i<n;i++ { if obstacleGrid[0][i] == 1 { break //当碰到obstacle后，后面所有的dp值就不用再设置了，直接利用其初始化值0 } else { dp[i] = 1 } } for i := 1; i < m; i++ { if obstacleGrid[i][0] == 1 { dp[0] = 0 } // 对dp[0]进行检查 for j := 1; j < n; j++ { // 在进行dp更新时，碰上obstacle该dp[i]需要置为0, if obstacleGrid[i][j] == 1 { dp[j] = 0 } else { dp[j] = dp[j] + dp[j-1] } } } return dp[n-1] }