这是一个典型的组合数学与动态规划相结合的问题。我们需要计算从起点 (1,1) 到终点 (n,n) 的所有可能路径的数量,每一步只能向右或向下移动一个格子。通过分析小规模的情况,我们可以总结出适用于任意 n 的递推关系,从而高效地解决问题。
给定一个大小为 n×n 的二维矩阵,计算从起点 (1,1) 到终点 (n,n) 的所有可能路径的数量。每一步可以向右或向下移动一个格子。
输入包含一个整数 n,表示矩阵的大小。 1<=n<=17
输出一个整数,表示从 (1,1) 到 (n,n) 的路径总数。
输入
3
输出
6
在 3×3 的矩阵中,从 (1,1) 到 (3,3) 的路径共有 6 种可能。