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”的情况： alt

心有成算

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

另辟蹊径

由于“不可逆”，所以从起点到终点走的总步数是确定的，向下或向右走的步数也是确定的。例如，当输入为 $m\times 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)$ 空间复杂度：使用n+m的变量出来存储输入，故空间复杂度为 $O (m + n)$

题解 | #走方格的方案数#