动态编程 - 带乘法器的板

Question

我得到了相当标准的DP问题 - 用整数登上nxn，都是积极的。我想在第一行的某个地方开始，在最后一行的某个地方结束并尽可能多地积累总和。从字段(i,j)我可以去领域(i+1, j-1)，(i+1, j)，(i+1, j+1)。这是相当标准的DP问题。但是我们添加了一件事 - 字段上可以有一个星号，而不是数字。如果我们遇到星号，那么我们就得到了0积分，但我们将乘数增加1。我们在遍历期间收集的所有数字都乘以multiplier。我不知道如何用这个乘数来解决这个问题。我认为这仍然是一个DP问题 - 但如何让方程式适合它？

谢谢你的帮助。

Answer 1

您仍然可以使用DP，但是您必须跟踪两个值：“基础”值，即没有应用任何乘数，以及“有效”值，即乘数。你通过网格向后工作，从前一行开始，在那之后得到行中的三个“相邻”单元格（路径上可能的“下一个”单元格），然后选择一个最高价值。

如果当前单元格是*，则得到base + effective最大的单元格，否则你只得到effective得分最高的单元格。

这是Python中的一个示例实现。请注意，而不是*我只是使用0作为乘数，而我是按顺序循环网格而不是反向，只是因为它更方便。

import random

size = 5
grid = [[random.randint(0, 5) for _ in range(size)] for _ in range(size)]
print(*grid, sep="\n")

# first value is base score, second is effective score (with multiplier)
solution = [[(x, x) for x in row] for row in grid]

for i in range(1, size):
    for k in range(size):
        # the 2 or 3 values in the previous line
        prev_values = solution[i-1][max(0, k-1):k+2]
        val = grid[i][k]
        if val == 0:
            # multiply
            base, mult = max(prev_values, key=lambda t: t[0] + t[1])
            solution[i][k] = (base, base + mult)
        else:
            # add
            base, mult = max(prev_values, key=lambda t: t[1])
            solution[i][k] = (val + base, val + mult)

print(*solution, sep="\n")
print(max(solution[-1], key=lambda t: t[1]))

示例：随机5x5网格，0对应*：

[4, 4, 1, 2, 1]
[2, 0, 3, 2, 0]
[5, 1, 3, 4, 5]
[0, 0, 2, 4, 1]
[1, 0, 5, 2, 0]

具有基值和有效值的最终solution网格：

[( 4,  4), ( 4,  4), ( 1,  1), ( 2,  2), ( 1,  1)]
[( 6,  6), ( 4,  8), ( 7,  7), ( 4,  4), ( 2,  4)]
[( 9, 13), ( 5,  9), ( 7, 11), (11, 11), ( 9,  9)]
[( 9, 22), ( 9, 22), ( 9, 13), (11, 15), (12, 12)]
[(10, 23), ( 9, 31), (14, 27), (13, 17), (11, 26)]

因此，这个网格的最佳解决方案是来自31的(9, 31)。向后穿过网格solution网格，这对应于路径0-0-5-0-4，即3*5 + 4*4 = 31，因为在*之前有2个5，在*之前有3个4。