【动态规划2】二维矩阵路线方案数问题

题解

解题思路

这是一个典型的组合数学与动态规划相结合的问题。我们需要计算从起点 $(1, 1)$ 到终点 $(n, n)$ 的所有可能路径的数量，每一步只能向右或向下移动一个格子。通过分析小规模的情况，我们可以总结出适用于任意 $n$ 的递推关系，从而高效地解决问题。

Step1: 讨论 (n = 3) 的情况

题目描述

给定一个大小为 $n \times n$ 的二维矩阵，计算从起点 $(1, 1)$ 到终点 $(n, n)$ 的所有可能路径的数量。每一步可以向右或向下移动一个格子。

输入

输入包含一个整数 $n$，表示矩阵的大小。 $1<=n<=17$

输出

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

示例

输入

3

输出

6

说明

在 $3 \times 3$ 的矩阵中，从 $(1, 1)$ 到 $(3, 3)$ 的路径共有 $6$ 种可能。