走方格的方案数

Posted on Edited on In ,

走方格的方案数_牛客题霸_牛客网

描述

请计算 n * m 的棋盘格子（ n 为横向的格子数，m 为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
注：沿棋盘格之间的边缘线行走, 数据范围： 1 <= n, m <= 8

输入描述：

输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述：

输出一行结果

示例1

输入：2 2
输出：6

解1

在这个棋盘中，你只能往右或往下走，所以你可以把它看作是在一个二维平面上走迷宫，每次只能向右或向下走一步。这样的话，你从左上角出发，要走到右下角，就必须走 $n$ 步向右和 $m$ 步向下。

因为你每次只能选择向右或向下走，所以这里的问题就转化成了在 $n+m$ 步的序列中选择 $m$ 个数作为向下走的步数，剩余的 $n$ 个数就是向右走的步数。这样的话，你就可以使用组合数的概念来计算答案。

你可以使用以下代码来计算答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function numOfWays(n: number, m: number): number {
  // 由于要选择 m-1 个数，所以可以使用组合数公式计算答案
  return factorial(n + m) / (factorial(m) * factorial(n));
}

// 阶乘函数
function factorial(n: number): number {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

// 测试
console.log(numOfWays(2, 2)); // 6

解2

我们可以建立一个二维数组 dp，其中 dp[i][j] 表示从起点走到位置 (i, j) 的方案数。
那么，我们就可以用如下的方程来求解这个问题：

1
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

这个方程的意思是，从位置 (i, j) 可以走到的方案数就是从位置 (i - 1, j) 和位置 (i, j - 1) 走到位置 (i, j) 的方案数之和。

我们可以用以下的代码来实现这个算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function numOfWays(n: number, m: number): number {
  // 初始化 dp 数组
  const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));

  // 初始化边界条件
  for (let i = 0; i <= n; i++) {
    dp[i][0] = 1;
  }
  for (let j = 1; j <= m; j++) {
    dp[0][j] = 1;
  }

 // 循环求解 dp 数组
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[n][m];
}