algorithm - 动态编程-带有乘法器的电路板

我得到了相当标准的dp问题板nxn整数，都是正的。我想从第一行的某个地方开始，到最后一行的某个地方结束，尽可能多地积累和。从field(i,j)我可以转到fields(i+1, j-1)，(i+1, j)，(i+1, j+1)。
这是相当标准的dp问题。但是我们要加上一件事-字段上可以有一个星号，而不是数字。如果我们遇到星号，那么我们得到了它的0点，但是我们增加了1的乘数我们稍后在遍历过程中收集的所有数字都乘以multiplier。
我不知道如何用乘法器来解决这个问题我认为这仍然是一个DP问题-但是如何得到正确的方程呢？
谢谢你的帮助。

最佳答案

您仍然可以使用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。

关于algorithm - 动态编程-带有乘法器的电路板，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47895509/