独一无二的路用递归算法怎么计算？

Question

独一无二的路

‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

描述

从前有一只小小的机器人叫小器，小器站在一个M*N的格子地板的最左上角，很孤单，它想到处去看看，经过不懈的努力它终于可以（只能）向下或者向右移动啦，它有一个宏伟的愿望就是要穿过格子地板到达右下角的砖，所以如果小器告诉你M和N，你能不能帮它计算一下这中间可以有多少条独一无二的路径（从左上角到右下角）？‪‪‪‪‪‫‪‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

‪‪‪‪‪‫‪提示：使用函数递归调用。m*n 问题可以分解为m*（n-1）和（m-1）* n 两个问题。‪‪‪‪‪‫‪‪‪‪‪‫‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

输入输出示例

输入格式：两个数字（m和n）中间以逗号（,）间隔‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

输出格式：数字‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬

输入输出示例1: 输入：3,3    输出：6

              示例2：输入：1,10  输出：1

我写的代码：

def way(n,m,i,j):
    if i==m or j==n:
        return 0
    elif i==m-1 and j==n-1:
        return 1
    elif i==m-1 and j!=n-1:
        return way(m,n,i,j+1)
    elif i!=m-1 and j==n-1:
        return way(m,n,i+1,j)
    else:
        return way(m,n,i+1,j)+way(m,n,i,j+1)
n=int(input())
m=int(input())
print(way(m,n,0,0))

测试结果完全不对，连输出都没有

Answer 1

def way(m, n, i, j):
    if i == m or j == n:
        return 0
    elif i == m - 1 and j == n - 1:
        return 1
    elif i == m - 1 and j != n - 1:
        return way(m, n, i, j + 1)
    elif i != m - 1 and j == n - 1:
        return way(m, n, i + 1, j)
    else:
        return way(m, n, i + 1, j) + way(m, n, i, j + 1)


m = int(input())
n = int(input())
print(way(m, n, 0, 0))

修改处：
1）def way(m, n, i, j): 原参数顺序搞反了。
2）m = int(input())
n = int(input())：到底先输入哪个？
因为没多少时间，我没仔细研究你的算法。原题意思都没彻底搞懂。但用给出的两组数据测试，结果均对。
其它，数据测试通过否？我就不知道了。

本答复由 大侠(AhcaoZhu)原创，转载请声明。
链接: https://blog.csdn.net/Ahcao2008