版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

问题描述

如下图所示,从矩阵(m*n)的(0, 0)出发,然后只能向下、向右,到达矩阵的对角(m-1, n-1)

求从(0,0)到(m-1, n-1) 一共有多少种走法

此处输入图片的描述

解题思路

解决这个问题,我们可以参考动态规划的思想
要到达(m-1, n-1), 就必须到达(m-2, n-1)或者(m-1, n-2)
从(m-2, n-1)到(m-1, n-1) 只有一种走法
从(m-1, n-2)到(m-1, n-1) 只有一种走法
那么从(0, 0)到(m-1, n-1)的走法数量

f(m-1, n-1) = f(m-2, n-1) + f(m-1, n-2)

递归算法

采用递归算法可以很容易写出代码

def try_walk(m, n):
    if m == 1 and n == 1:
        return 0
    return walk(m -1, n -1)

def walk(x, y):
    if x == 0 and y == 0:
        return 1

    res = 0
    if x - 1 >= 0:
        res += walk(x - 1, y)

    if y - 1 >= 0:
        res += walk(x, y - 1)

    return res

if __name__ == '__main__':
    print (1,1), try_walk(1, 1)
    print (1,2), try_walk(1, 2)
    print (2,2), try_walk(2, 2)
    print (2,3), try_walk(2, 3)
    print (3,3), try_walk(3, 3)

参考动态规划的思想,可以记录cache (x,y)到(0,0) 走法的数量,加快速度

def try_walk(m, n):
    if m == 1 and n == 1:
        return 0

    matrix = []
    for i in range(m):
        a = []
        for j in range(n):
            a.append(-1)
        matrix.append(a)

    return walk(m -1, n -1, matrix)

def walk(x, y, matrix):

    if x == 0 and y == 0:
        return 0

    # print(x, y)
    if matrix[x][y] != -1:
        return matrix[x][y]

    res = 0
    if x - 1 >= 0:
        res += walk(x - 1, y, matrix)

    if y - 1 >= 0:
        res += walk(x, y - 1, matrix)

    return res

if __name__ == '__main__':
    print (1,1), try_walk(1, 1)
    print (1,2), try_walk(1, 2)
    print (2,2), try_walk(2, 2)
    print (2,3), try_walk(2, 3)
    print (3,3), try_walk(3, 3)

非递归算法

由于要计算出f(x, y),必须先算出计算出f(x -1, y) 和f(x, y – 1)
(x – 1, y) 在 (x, y) 的上边, (x, y – 1) 在 (x, y) 的左边
因此只需要按矩阵,逐行, 每行中再逐列计算即可

def try_walk(m, n):
    if m == 1 and n == 1:
        return 0

    matrix = []
    for i in range(m):
        a = []
        for j in range(n):
            a.append(0)
        matrix.append(a)

    matrix[0][0] = 1
    for i in range(m):
        for j in range(n):
            if i - 1 >= 0:
                matrix[i][j] += matrix[i-1][j]
            if j - 1 >= 0:
                matrix[i][j] += matrix[i][j - 1]

    return matrix[m-1][n-1]


if __name__ == '__main__':
    print (1,1), try_walk(1, 1)
    print (1,2), try_walk(1, 2)
    print (2,2), try_walk(2, 2)
    print (2,3), try_walk(2, 3)
    print (3,3), try_walk(3, 3)

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据