题目描述

给定一个 $n \times n$ 的二维网格，你从左上角 $(0, 0)$ 出发，可以选择往下走或者往右走。每次走一步，你可以选择往下移动一格或者往右移动一格。请计算从 $(0, 0)$ 到 $(n-1, n-1)$ 的不同路径数。

输入

输入包含一个整数 $n$ （$1 \leq n \leq 15$），表示网格的大小。

输出

输出一个整数，表示从 $(0, 0)$ 到 $(n-1, n-1)$ 的不同路径数。

示例

输入

3

输出

6

提示

• 对于 $n = 3$，可以通过以下 6 条路径从坐标 $(0, 0)$ 到坐标 $(2, 2)$：
  1. 右 -> 右 -> 下 -> 下
  2. 右 -> 下 -> 右 -> 下
  3. 右 -> 下 -> 下 -> 右
  4. 下 -> 右 -> 右 -> 下
  5. 下 -> 右 -> 下 -> 右
  6. 下 -> 下 -> 右 -> 右

这是从坐标 $(0, 0)$ 到坐标 $(n-1, n-1)$ 的不同路径数。

【递归4】路径统计①

题目描述

给定一个 $n \times n$ 的二维网格，从左上角 $(0, 0)$ 出发，你可以选择往下走或者往右走。每次走一步，你可以选择往下移动一格或者往右移动一格。请计算从 $(0, 0)$ 到 $(n-1, n-1)$ 的不同路径数。

思路分析

本题是典型的动态规划或递归问题，下面通过递归的方法来求解。

1. 递归定义：

• 设定一个递归函数 uniquePaths(x, y)，表示从位置 $(x, y)$ 到达右下角 $(n-1, n-1)$ 的不同路径数。每次只能向右或向下走。因此，从当前位置 $(x, y)$ 到 $(n-1, n-1)$ 的路径数，可以分解为两种情况：
  • 向右走：如果我们从当前位置向右走，问题就变成计算从 $(x, y+1)$ 到 $(n-1, n-1)$ 的路径数。
  • 向下走：如果我们从当前位置向下走，问题就变成计算从 $(x+1, y)$ 到 $(n-1, n-1)$ 的路径数。

对应代码：

def uniquePaths(x, y, n):
    # 基本情况：如果到达右下角 (n-1, n-1)，返回 1
    if x == n - 1 and y == n - 1:
        return 1

    paths = 0

    # 向下走
    if x < n - 1:
        paths += uniquePaths(x + 1, y, n)  # 递归计算向下走的路径数

    # 向右走
    if y < n - 1:
        paths += uniquePaths(x, y + 1, n)  # 递归计算向右走的路径数

    return paths

在这个步骤中，我们通过递归将问题分解为向右走和向下走两种情况的路径数累加。

2. 递归终止条件：

• 当我们到达右下角 $(n-1, n-1)$ 时，路径数为 1，因为已经到达目标点。

对应代码：

# 基本情况：如果到达右下角 (n-1, n-1)，返回 1
if x == n - 1 and y == n - 1:
    return 1

这个条件确保我们在到达目标时停止递归，并返回 1 表示到达了一条有效路径。

3. 边界条件：

• 如果当前已经到达网格的最后一行或最后一列，那么只能一直向右或一直向下走，路径数只有一种可能：
  • 如果当前在最后一行，则只能向右走。
  • 如果当前在最后一列，则只能向下走。

对应代码：

# 向下走
if x < n - 1:
    paths += uniquePaths(x + 1, y, n)

# 向右走
if y < n - 1:
    paths += uniquePaths(x, y + 1, n)

当到达网格的最后一行或最后一列时，代码会确保只向右或只向下走。递归会自动停止，当路径到达右下角时，返回 1。

4. 递归计算过程：

• 从左上角 $(0, 0)$ 开始递归计算路径数，直到到达右下角 $(n-1, n-1)$。

对应代码：

if __name__ == "__main__":
    n = int(input())  # 输入网格的大小
    print(uniquePaths(0, 0, n))  # 从 (0, 0) 出发

这里，我们在主函数中输入网格的大小 ( n )，然后调用递归函数 uniquePaths(0, 0, n) 从左上角开始计算路径数。

时间复杂度

递归的时间复杂度为 O(2^(m+n))，其中 ( m ) 和 ( n ) 是网格的尺寸。每个步骤都有两种选择（向下或向右），因此递归的深度为 ( m+n )，递归树的大小是指数级的。

Python代码实现

def uniquePaths(x, y, n):
    # 基本情况：如果到达右下角 (n-1, n-1)，返回 1
    if x == n - 1 and y == n - 1:
        return 1

    paths = 0

    # 向下走
    if x < n - 1:
        paths += uniquePaths(x + 1, y, n)  # 递归计算向下走的路径数

    # 向右走
    if y < n - 1:
        paths += uniquePaths(x, y + 1, n)  # 递归计算向右走的路径数

    return paths

# 主函数
if __name__ == "__main__":
    n = int(input())  # 输入网格的大小
    print(uniquePaths(0, 0, n))  # 从 (0, 0) 出发