本文共 472 字，大约阅读时间需要 1 分钟。

递归思想是解决这类经典问题的高效方法。在这个问题中，我们可以通过递归地拆解问题来简化计算。

递归思路解析

我们可以将问题分解为两个更小的子问题：

将路径数相加即可得到总数。这两个子问题本身又可以继续分解，直到达到最简情况（即m=0或n=0时，只有一种路径）。

代码示例

#include 
   
     using namespace std;int pathnum(int m, int n) {    if (m == 0 || n == 0)        return 1;    return pathnum(m-1, n) + pathnum(m, n-1);}int main() {    int m, n;    while (cin >> m >> n) {        cout << pathnum(m, n) << endl;    }}
   

优化解法

这种递归方法虽然直观，但计算量较大。可以通过记忆化查找和动态规划来优化性能。