具有给定起点的矩阵中的最大和路径

Question

我正在学习解决类似类型的动态规划问题以在矩阵中找到最大路径和。

我在下面的网站上学习了这个算法。

我要解决的问题与网站上的有点不同。

该网站的算法利用 max() 更新矩阵中的值以找到最大值以创建最大路径。

例如，给定一个数组：

sample = [[110, 111, 108, 1],
          [9, 8, 7, 2],
          [4, 5, 10, 300],
          [1, 2, 3, 4]]

最佳求和路径为 111 + 7 + 300 + 4 = 422

在上面的示例中，算法通过查找矩阵第一行的最大值来找到第一条路径。

我的问题是，如果必须指定算法的起点怎么办。值 h 作为开始的第一个元素给出。

例如，给定上面的样本数组，如果 h = 0，我们需要从样本 [0][h] 开始，因此最佳路径是

110（我们的起点）+ 8 + 10 + 4 = 132

如您所见，路径只能向下或相邻，因此如果我们从 h = 0 开始，将会有一些值我们无法达到某些值，例如 300。

这是我在 O(N*D) 复杂度内解决这个问题的混乱尝试，

# Find max path given h as a starting point
def find_max_path_w_start(mat, h):
    res = mat[0][0]
    M = len(mat[0])
    N = len((mat))

    for i in range(1, N):
        res = 0
        for j in range(M):
            # Compute the ajacent sum of the ajacent values from h
            if i == 1:
                # If h is starting area, then compute the sum, find the max
                if j == h:
                    # All possible
                    if (h > 0 and h < M - 1):
                        mat[1][h + 1] += mat[0][h]
                        mat[1][h] += mat[0][h]
                        mat[1][h - 1] += mat[0][h]
                        print(mat)
                    # Diagona Right not possible
                    elif (h > 0):
                        mat[1][h] += mat[0][h]
                        mat[1][h - 1] += mat[0][h]
                    # Diagonal left not possible
                    elif (h < M - 1):
                        mat[1][h] += mat[0][h]
                        mat[1][h + 1] += mat[0][h]
                # Ignore value that has been filled.
                elif j == h + 1 or j == h - 1 :
                    pass
                # Other elements that cannot reach, make it -1
                elif j > h + 1 or j < h - 1:
                    mat[i][j] = -1
            else:
                # Other elements that cannot reach, make it -1
                if j > h + 1 or j < h - 1:
                    mat[i][j] = -1
                else:
                    # When all paths are possible
                    if (j > 0 and j < M - 1):
                        mat[i][j] += max(mat[i - 1][j],
                                         max(mat[i - 1][j - 1],
                                             mat[i - 1][j + 1]))
                    # When diagonal right is not possible
                    elif (j > 0):
                        mat[i][j] += max(mat[i - 1][j],
                                         mat[i - 1][j - 1])
                    # When diagonal left is not possible
                    elif (j < M - 1):
                        mat[i][j] += max(mat[i - 1][j],
                                         mat[i - 1][j + 1])

            res = max(mat[i][j], res)

    return res

我的方法是只存储可达值，例如如果我们从 h = 0 开始，因为我们从 mat[0][h] 开始，我们只能计算 当前和bottom max(mat[1][h] and 当前和相邻右的总和 mat[1][h + 1])，对于其他值我将其标记为-1以将其标记为无法访问。

这不是 return 最后的预期总和。

我的逻辑有问题吗？我需要存储其他值才能完成此操作吗？

Answer 1

在这里构建自下而上的解决方案很容易。开始思考只有一两行的情况，并扩展它以轻松理解该算法。
注意：这会修改原始矩阵而不是创建新矩阵。如果您需要在同一个矩阵上多次运行函数，则需要创建矩阵的副本来执行相同的操作。

def find_max_path_w_start(mat, h):
    res = mat[0][0]
    M = len(mat[0])
    N = len((mat))

    # build solution bottom up
    for i in range(N-2,-1,-1):
        for j in range(M):
            possible_values = [mat[i+1][j]]
            if j==0:
                possible_values.append(mat[i+1][j+1])
            elif j==M-1:
                possible_values.append(mat[i+1][j-1])
            else:
                possible_values.append(mat[i+1][j+1])
                possible_values.append(mat[i+1][j-1])
            mat[i][j] += max(possible_values)
    return mat[0][h]

sample = [[110, 111, 108, 1],
          [9, 8, 7, 2],
          [4, 5, 10, 300],
          [1, 2, 3, 4]]

print(find_max_path_w_start(sample, 0)) # prints 132

Answer 2

您可以将第一行除h之外的所有元素都设置为负无穷大，并像没有起点限制一样计算答案。

比如把这段代码放在你代码的开头

for i in range(M):
    if i != h:
        mat[0][i] = -1e100

Answer 3

这是一个与您的解决方案类似的解决方案，但它只计算可能从 h 开始的矩阵值的路径总和。

def find_max_path_w_start(mat, h):
    M = len(mat[0])
    N = len((mat))

    for i in range(1, N):
        # `h - i` is the left hand side of a triangle with `h` as the top point.
        # `max(..., 0)` ensures that is is at least 0 and in the matrix.
        min_j = max(h - i, 0)

        # similar to above, but the right hand side of the triangle.
        max_j = min(h + i, M - 1)

        for j in range(min_j, max_j + 1):
            # min_k and max_k are the start and end indices of the points in the above
            # layer which could potentially lead to a correct solution.
            # Generally, you want to iterate from `j - 1` up to `j + 1`,
            # however if at the edge of the triangle, do not take points from outside the triangle:
            # this leads to the `h - i + 1` and `h + i - 1`.
            # The `0` and `M - 1` prevent values outside the matrix being sampled.
            min_k = max(j - 1, h - i + 1, 0)
            max_k = min(j + 1, h + i - 1, M - 1)

            # Find the max of the possible path totals
            mat[i][j] += max(mat[i - 1][k] for k in range(min_k, max_k + 1))
            
    # Only sample from items in the bottom row which could be paths from `h`
    return max(mat[-1][max(h - N, 0):min(h + N, M - 1) + 1])


sample = [[110, 111, 108, 1],
          [9, 8, 7, 2],
          [4, 5, 10, 300],
          [1, 2, 3, 4]]

print(find_max_path_w_start(sample, 0))

具有给定起点的矩阵中的最大和路径

Maximum sum path in the matrix with a given starting point

python

algorithm

dynamic-programming