题目信息

image.png

问题解答

https://leetcode-cn.com/submissions/detail/127256854/
到当前路径的走法 = 到左边格子的走法 + 到上边格子的走法，先初始化第一行和第一列的走法，都只有一种，剩下的格子就可以用下面这个算法推导出来。
核心算法：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

  1. function uniquePaths(m: number, n: number): number {
  2.     let dp = Array.from({length: m}, () => Array.from({length: n}, () => 0))
  4.     for(let i = 0; i < m; i++) {
  5.         dp[i][0] = 1
  6.     }
  8.     for(let j = 0; j < n; j++) {
  9.         dp[0][j] = 1
  10.     }
  12.     for(let i = 1; i < m; i++) {
  13.         for(let j = 1; j < n; j++) {
  14.             dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  15.         }
  16.     }
  18.     return dp[m - 1][n - 1] 
  19. };