62. 不同路径.md

62. 不同路径

题目传送门

点击这里

解题思路

这道题典型的动态规划题，我们可以建立二维动态规划数组dp[i][j]表示走到(i, j)位置处可以有多少条路径，因为每次只能移动一次且只能向右向下，所以可以得出状态转移方程dp[i][j] = dp[i-1][j] + dp[i][j-1]，但是有限制条件，这里也是边界条件，在边界的点只能由一种方向移动过来，所以可以得到dp[i][0] = 1和dp[0][i] = 1

代码

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-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
    
}