【递归4】路径统计①

题目描述

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

思路分析

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

题目描述

给定一个 $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)$ 的不同路径数。