HJ91 走方格的方案数 题解

by 限时烟花

抽丝剥茧

这个题干非常简单，也是大家在中学阶段经常遇到的一个数学问题——不可逆行走问题。 即，从左上角走到右下角，且只能向右和向下行走。

化繁为简

根据大家比较熟悉的思路，我们可以使用递归的方法来将大的问题分解为小的子问题。

马上行动

def func(x,y):
    if x < 0 or y < 0:
        return 0
    elif x == 0 or y == 0:
        return 1
    else:
        return func(x-1, y)+func(x, y-1)
 
while True:
    try:
        n, m = map(int, input().split())
        res = func(n, m)
        print(res)
    except:
        break

例题图解

下面使用图解来展示一下输入为“2 2”的情况：

心有成算

1. 时间复杂度：因为使用了递归，且递归的最大深度为$m+nm+n$,故时间复杂度为$O(m+n)O(m+n)$
2. 空间复杂度：因为使用了$m\times nm\backslash times\; n$大小的空间，故空间复杂度为$O(mn)O(mn)$

另辟蹊径

由于“不可逆”，所以从起点到终点走的总步数是确定的，向下或向右走的步数也是确定的。例如，当输入为$m\times nm\backslash times\; n$时，需要走的总步数也就一定是$(m+n)(m+n)$步。同时为了能够走到右下方，一定需要向下走m步，向右走n步。 故也可以使用组合数来完成。即把这个问题抽象为从(m+n)步中挑出m步向下走的种数。

import math

    
while True:
    try:
        row, col = map(int, input().split())
        total_step = col + row
        res = math.factorial(total_step) / (math.factorial(col) * math.factorial(row))
        print(int(res))
    except:
        break

时间复杂度：由于使用阶乘函数复杂度为$O(m+n)O(m+n)$，故时间复杂度为$O(m+n)O(m+n)$ 空间复杂度：使用n+m的变量出来存储输入，故空间复杂度为$O(m+n)O(m+n)$