62.不同路径.md

62.不同路径

/*
 * @lc app=leetcode.cn id=62 lang=typescript
 *
 * [62] 不同路径
 */

// @lc code=start
function uniquePaths(m: number, n: number, cache: { [key: string]: number } = {}): number {}
// @lc code=end

解法 1: 递归

• 时间复杂度:
• 空间复杂度:

function uniquePaths(m: number, n: number, cache: { [key: string]: number } = {}): number {
  if (m === 1 || n === 1) return 1
  if (cache[`${m},${n}`]) return cache[`${m},${n}`]
  const result = uniquePaths(m, n - 1, cache) + uniquePaths(m - 1, n, cache)
  cache[`${m},${n}`] = result
  return result
}

解法 2: 动态规划

• 时间复杂度:

• 空间复杂度:

• 子问题: 求 0,0 到 i,j 的有多少条不同路径

• 状态: dp[i][j] 表示从 0,0 到 i,j 的不同路径数量

• 递推公式: dp[i][j]=dp[i-1][j]+dp[i][j-1]

  • 优化空间: dp[j]+=dp[j-1]

• 边界: dp[0][j]=1,dp[i][0]=1

function uniquePaths(m: number, n: number): number {
  const cur = new Array(n).fill(1)
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      cur[j] += cur[j - 1]
    }
  }
  return cur[n - 1]
}

Case

test.each([
  { input: { m: 3, n: 7 }, output: 28 },
  { input: { m: 3, n: 2 }, output: 3 },
  { input: { m: 7, n: 3 }, output: 28 },
  { input: { m: 3, n: 3 }, output: 6 },
  { input: { m: 51, n: 9 }, output: 1916797311 },
])('input: m = $input.m, n = $input.n', ({ input: { m, n }, output }) => {
  expect(uniquePaths(m, n)).toBe(output)
})