尝试确定最大成本路径,但仅适用于大小为2和3的矩阵

因此,在这里,我们编写了一些非常丑陋的代码,其目的是在给定任意大小的矩阵的情况下,找到从矩阵的中心导航到拐角之一的最高成本路径,并返回一个表示成本的int值。穿过那条路。

在这种情况下,如果大小为2或3,但程序没有其他大小,则程序可以正常工作。

如果大小为1,则会出现超出范围的错误,但是如果大小为4或更大,它将简单地返回0。我知道该错误在maxCostPaths函数中,但我无法弄清楚是什么原因引起的。

我注意到,当maxCostPaths填满时,maxCostPath矩阵将跳过右侧,因此最终得到一个看起来像这样的矩阵。

[0,1,2,0]

[3,4,5,0]

[4,5,6,0]

[5.6.8.0]

我也知道这段代码太可怕了,所以如果有人可以建议/演示一种通过动态编程来实现这一目标的更好方法,请告诉我。

    cost = max(maxCostPathBottomLeft(building), maxCostPathBottomRight(building), maxCostPathTopLeft(building),
               maxCostPathTopRight(building))
    print("Cost to reach : ", cost)


def maxCostPaths(matrix):
    maxCostPath = [[0 for x in range(len(matrix))] for y in range(len(matrix))]
    print(len(matrix))
    for i in range(0, int(len(matrix)/2) + 2):
        aboveCost = maxCostPath[i - 1][0]
        maxCostPath[i][0] = aboveCost + matrix[i][0]

    for j in range(0, int(len(matrix)/2 + 2)):
        leftCost = maxCostPath[0][j - 1]
        maxCostPath[0][j] = leftCost + matrix[0][j]

    for i in range(0, int(len(matrix)/2) + 2):
        for j in range(0, int(len(matrix)/2) + 2):
            leftCost = maxCostPath[i - 1][j]
            aboveCost = maxCostPath[i][j - 1]
            maxCostPath[i][j] = matrix[i][j] + max(leftCost, aboveCost)
    print(maxCostPath)
    print(maxCostPath[len(matrix) - 1][len(matrix) - 1])
    return maxCostPath[len(matrix) - 1][len(matrix) - 1]


def maxCostPathBottomRight(matrix):
    maxCostPath = [[0 for x in range(matrix.size + 1)] for y in range(matrix.size + 1)]
    center = int(matrix.size)
    b = 0
    for a in range(center, matrix.size * 2 + 1):
        d = 0
        for c in range(center, matrix.size * 2 + 1):
            maxCostPath[b][d] = matrix.rooms[a][c].food
            d += 1
        b += 1
    return maxCostPaths(maxCostPath)


def maxCostPathBottomLeft(matrix):
    maxCostPath = [[0 for x in range(matrix.size + 1)] for y in range(matrix.size + 1)]
    center = int(matrix.size)
    b = 0
    for a in range(center, matrix.size * 2 + 1):
        d = 0
        for c in range(0, matrix.size + 1):
            maxCostPath[b][d] = matrix.rooms[a][c].food
            d += 1
        b += 1
    return maxCostPaths(maxCostPath)


def maxCostPathTopRight(matrix):
    maxCostPath = [[0 for x in range(matrix.size + 1)] for y in range(matrix.size + 1)]
    center = int(matrix.size)
    b = 0
    for a in range(center, matrix.size * 2 + 1):
        d = 0
        for c in range(0, matrix.size + 1):
            maxCostPath[b][d] = matrix.rooms[a][c].food
            d += 1
        b += 1
    return maxCostPaths(maxCostPath)


def maxCostPathTopLeft(matrix):
    maxCostPath = [[0 for x in range(matrix.size + 1)] for y in range(matrix.size + 1)]
    center = int(matrix.size)
    b = 0
    for a in range(0, matrix.size + 1):
        d = 0
        for c in range(0, matrix.size + 1):
            maxCostPath[b][d] = matrix.rooms[a][c].food
            d += 1
        b += 1
    return maxCostPaths(maxCostPath)
评论