不同路径

62. 不同路径

leetcode 链接

思路：

动态规划

1. dp[i][j] 表示到达 i，j 坐标时，总共有 dp[i][j]不同条路径。

2. 初始化 dp 数组，dp[i][0] = 1, dp[0][j] = 1。

3. 确定遍历方向，从前往后遍历。

4. 确定转换方程，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

5. 确定结束条件，遍历到最后一个坐标，返回 dp[m - 1][n - 1] 即可。

typescript 解法

function uniquePaths(m: number, n: number): number {
  // 确定dp数组含义，dp表示到达i，j坐标时，总共有dp[i][j]不同条路径.
  // 初始化dp数组
  const dp: number[][] = new Array(m).fill(1).map(() => new Array(n).fill(1));
  // 确定遍历方向
  for (let i: number = 1; i < m; i++) {
    for (let j: number = 1; j < n; j++) {
      // 确定转换方程
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

go 解法

func uniquePaths(m int, n int) int {
    // dp[i][j] 表示到达i,j 坐标时，有dp[i][j]种不同的路径
    dp := make([][]int, m)
    // 初始化dp数组
    for i := 0; i < m; i ++ {
        dp[i] = make([]int, n)
        for j := 0; j < n; j ++ {
            if i == 0 || j == 0 {
                dp[i][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]
}