【递归4】路径统计①
题解
题面描述
给定一个 n×n 的二维网格,你从左上角 (0,0) 出发,可以选择往下走或者往右走。每次走一步,你可以选择往下移动一格或者往右移动一格。请计算从 (0,0) 到 (n−1,n−1) 的不同路径数。
题目描述
给定一个 n×n 的二维网格,你从左上角 (0,0) 出发,可以选择往下走或者往右走。每次走一步,你可以选择往下移动一格或者往右移动一格。请计算从 (0,0) 到 (n−1,n−1) 的不同路径数。
输入
输入包含一个整数 n (1≤n≤15),表示网格的大小。
输出
输出一个整数,表示从 (0,0) 到 (n−1,n−1) 的不同路径数。
示例
输入
3
输出
6
提示
- 对于 n=3,可以通过以下 6 条路径从坐标 (0,0) 到坐标 (2,2):
- 右 -> 右 -> 下 -> 下
- 右 -> 下 -> 右 -> 下
- 右 -> 下 -> 下 -> 右
- 下 -> 右 -> 右 -> 下
- 下 -> 右 -> 下 -> 右
- 下 -> 下 -> 右 -> 右
这是从坐标 (0,0) 到坐标 (n−1,n−1) 的不同路径数。