题目描述

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

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

题解

解题思路

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

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