62. 不同路径

62. 不同路径

代码

javascript

// 62. 不同路径：https://leetcode.cn/problems/unique-paths/description/
// 输入：m = 3, n = 7
// 输出：28

export function uniquePaths (m, n) {
  const f = new Array(m).fill(0).map(_ => new Array(n).fill(0))
  for (let i = 0; i < m; i++) {
    f[i][0] = 1
  }

  for (let j = 0; j < n; j++) {
    f[0][j] = 1
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1]
    }
  }

  return f[m - 1][n - 1]
}

typescript

// 62. 不同路径：https://leetcode.cn/problems/unique-paths/description/
// 输入：m = 3, n = 7
// 输出：28

export function uniquePaths (m: number, n: number): number {
  const f: number[][] = new Array(m).fill(0).map(_ => new Array(n).fill(0))
  for (let i = 0; i < m; i++) {
    f[i][0] = 1
  }

  for (let j = 0; j < n; j++) {
    f[0][j] = 1
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1]
    }
  }

  return f[m - 1][n - 1]
}

测试代码

test

import { expect, test } from 'vitest'
import { uniquePaths } from './typescript.ts'
import { uniquePaths as uniquePathsJs } from './javascript.js'

test(`uniquePaths`, () => {
  expect(uniquePaths(3, 7)).toBe(28)
})

test(`uniquePathsJs`, () => {
  expect(uniquePathsJs(3, 7)).toBe(28)
})