python - 矩阵右下角有任意大小障碍物的方法数向右或向下跳过

Question

问题 - 你必须找到从初始位置可以到达的路径数量 (1,1) 到最终位置 (N,M) [哪里电话 是行数和 男 是列数]，假设:

您可以向下移动任意数量的步骤。

您可以向右移动任意数量的步骤。

注意:这里的数组索引是 1-indexed
一些条件:

你永远不能离开网格。

您不能忽略这些条件。

第一个单元格 (1,1) 和最后一个单元格 (N,M) 不包含障碍物。

空闲单元格由 表示. 障碍物用*表示。

示例测试用例:

>>> 3 3
    . . .
    . * .
    . . .

>>> 8

会有8种方式:

(1,1),(1,2),(1,3),(2,3),(3,3)

(1,1),(1,2),(1,3),(3,3)

(1,1),(1,3),(2,3),(3,3)

(1,1),(1,3),(3,3)

(1,1),(2,1),(3,1),(3,2),(3,3)

(1,1),(3,1),(3,2),(3,3)

(1,1),(2,1),(3,1),(3,3)

(1,1),(3,1),(3,3)

我的代码:

def ways(l):
    
   # Don't know how to proceed



Testcases=int(input())
lst=[]
for i in range(Testcases):
    N,M=input().split()
    N,M=int(N),int(M)
    for j in range(N):
        s=input().split(" ",M)
        lst.append(s)
    
    ways(lst)

我不知道如何继续。

Answer 1

当您处理此类问题时，您应该首先寻找可能出现在子问题中的一些模式。例如，您面临的一个子问题是找出沿对齐点移动的方式数。首先，建立一个表格，左边有点数，右边有到达最后一个点的方法数。

2  1
3  2
4  4
5  8
6  16
...

应该很清楚，模式是 number_of_ways = 2^(number_of_points - 2) .我不是数学家，所以不要问我为什么，但你可以很容易地证明它计算所有组合，也许使用动态规划。这是代码，或者你可以相信我(我强烈建议你不要这样做)

n = 12
dp = [None] * (n + 1)

def num_of_subset(n):
    if dp[n] != None:
        return dp[n]
    elif n == 1:
        return 1
    else:
        ways = 0
        for i in range(n):
            ways += num_of_subset(n - (i + 1))
        
        dp[n] = ways
        return ways
        
print(num_of_subset(n))

第一部分消失了，现在我们知道了一些让一切变得更容易的事情:每次添加一个新的“点”时，可能的方式重复的数量。

第二部分:有很多事情需要考虑:

您需要跟踪您有多少连续点和对齐点。为此，DP 表的每个条目都是一个元组，第一个和第二个元素是从顶部和左侧开始的计数器。

为了获得从起点到终点的总路径数，每个元组在最后一个索引中包含到达该特定单元格的总路径数。

障碍物距顶部和左侧的距离为 -1，单个孤立点距顶部和左侧的距离均为 0。第二个对齐点不会添加任何其他方式到达终点，因为您被迫通过它。相反，假设您正在查看上部单元格，从第 3 个对齐点开始，您将顶部单元格的方式加倍。

第一个单元格自动以元组的第三个索引中的 1 开始(到目前为止的计算方式)。这是因为如果你有一个单一的矩阵 1x1，那么有一种方法可以到达终点，那就是基本上什么都不做。

这有点难以解释，所以这里是代码:

rows = 3
cols = 3

matrix = """
    ...
    .*.
    ...
"""

matrix = [list(r) for r in matrix.split()]
print(matrix)

#(from_top_distance, from_left_distance, totways_until_here)
dp = [[(-1, -1, 0)] * cols for _ in range(rows)]

for ri, r in enumerate(matrix):
    for ci, c in enumerate(r):
        if c == '*':
            continue
        
        if ri == 0 and ci == 0:
            dp[ri][ci] = (0, 0, 1)
            continue
        
        if (ri == 0 or dp[ri - 1][ci][0] == -1) and (ci == 0 or dp[ri][ci - 1][1] == -1):
            dp[ri][ci] = (-1, -1, 0)
            continue
        
        from_top = 0 if ri == 0 else dp[ri - 1][ci][0] + 1
        from_left = 0 if ci == 0 else dp[ri][ci - 1][1] + 1
        
        top_value = 0 if ri == 0 \
            else dp[ri - 1][ci][2] if from_top < 2 \
            else dp[ri - 1][ci][2] * 2
            
        left_value = 0 if ci == 0 \
            else dp[ri][ci - 1][2] if from_left < 2 \
            else dp[ri][ci - 1][2] * 2
        
        dp[ri][ci] = (from_top, from_left, top_value + left_value)

print(dp)
print(dp[rows - 1][cols - 1][2])

这段代码的美妙之处(如果正确的话)是计算复杂度为O(M*N) .