algorithm - 动态编程:通过二维矩阵的总和(较硬的版本)

Question

这是我算法课上的，我想我真的需要一些帮助。
给定一个成本矩阵Happiness[][]，其中Happiness[i][j]表示使用坐标（i，j）访问单元格的幸福，则从右上角开始，到左下角结束我们想找到最大的幸福。
在矩阵中只能向下或向左。
但我们有两个限制：
1.您可以选择跳过零行或多行，这意味着您可以根据需要首先转到最后一行。
2.选择向左时，成本=成本-1。第二个连续的左键导致cost=cost-2，但是当您向下然后向左键时，它会刷新。
下面是一个例子：

这是步骤：

我不确定我是对是错。我用自上而下的。
我的解决方案：
要达到一个单元格矩阵[i][j]，您必须从一个更高的单元格或左到原始单元格。
我的复发：（我卡在这里）
我认为基本情况是最左边的行和最下面的列。
计算机如何检查连续步骤并知道是opt解决方案？
我知道把整个问题贴出来很奇怪，但我不能把问题简化得更好。。。

Answer 1

根据@____的评论，解决这个问题的诀窍是添加一个额外的维度，表示到达递归关系的单元格所用的左数。
注意：为了简化这个问题，我将给定矩阵的行颠倒，使允许的移动方向为向下和向右，起始单元格变为(0, 0)而结束单元格变为(W - 1, H - 1)，其中W和H分别是矩阵的宽度和高度。此外，矩阵和相应的最大幸福度dp表被认为是按行的主要顺序排列的，即matrix[y][x]是单元格(x, y)处的值。
我们真正的基本情况是访问起始单元的快乐，它要么matrix[0][0]要么0，这取决于起始单元的值是否必须包含在总快乐中。但是，我们也有两个伪基的情况比较简单的计算实际递归。
这些伪基本情况是最左边的列（记住，行已经反转，所以这是原始矩阵中最右边的列）和最上面的行最左边列中单元格(0, y)（1 <= y < H）的递归关系为：

h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in 0 to y-1)

其中， h是我们的最大幸福度dp表， h[y][x][r]是在到达 (0, 0)之前，从单元格 (x, y)到 r的最大幸福度（遵循给定的规则），取了 (x, y)个连续的右（或左，对于原始的非行反转矩阵）因此，如果 r为0，则最后遍历的单元格是当前单元格正上方的单元格到达最左边列中单元格的唯一可能方法是直接从它上面的单元格中获取。
对我们最大幸福表的一个重要的注意点是，对于所有细胞， (x, y)的最大幸福是由 h[y][x][r]的最大值赋予 r的所有值。如果 h是三维数组/列表，它也可以表示为 max(h[y][x])。
类似地，最上面一行的单元格 (x, 0)（ 1 <= x < W）的递归关系是：

h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x

这源于这样一个事实：到达最上面一行的单元格的唯一方法是继续从起始单元格向右移动。到达最上面一行单元格的权限数等于其基于0的X坐标，因此将受到 -x的惩罚。
现在我们有了基础病例，我们可以继续讨论细胞 (x, y)的复发关系，其中 1 <= x < W和 1 <= y < H。
在建立这种递归关系时，首先要注意的是，只有两种可能：最后一个单元格位于给定单元格的上方或左侧。我们将考虑这两种可能性。
如果最后一个单元格位于给定单元格之上，则其坐标为 (x, j)，其中 0 <= j < y为了获得最大的幸福，最后一间牢房的幸福也必须是最大的。因此，当最后一个单元格位于给定单元格之上时， (x, y)的最大幸福是由

h[y][x][0] = matrix[y][x] + max(max(h[j][x]) for j in 0 to y-1)

注意，所做的权利的数量（ r）是0，而 max(h[j][x])是以任意权限到达细胞 (x, j)所获得的最大幸福。
如果最后一个单元格在给定单元格的左侧（或者换句话说，最后一个移动是在右侧），那么它的坐标就是 (x - 1, y)。这是因为我们一次只能向右移动一个单元格。与前一种情况不同，最后一个单元格的位置是恒定的。但是，访问此单元格所需的连续权限（ r）数目是可变的因此，我们必须考虑 r的所有可能值。由于最小的1个权利和最大的 x权利可以作出， 1 <= r <= x。对于 r的每一个值，这个单元格的最大幸福度是对[cc]权利的左边（最后一个单元格）的最大幸福值加上 r - 1减去惩罚值（这只是 (x, y)）。在伪代码中，

for r in 1 to x:
    h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r

现在，我们已经拥有了以自下而上或自上而下的方式运行算法所需的一切我们的最终答案是，用“cc>”给出到达右下（右下行反向矩阵）的右下角的最大幸福值。
把所有的东西放在一起，我们有下面的（Python EXK）自下而上算法，时间复杂度 r - 1算法：

h[0][0][0] = matrix[0][0]

for x in range(1, W):
    h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x

for y in range(1, H):
    h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in range(y))

for y in range(1, H):
    for x in range(1, W):
        for r in range(1, x + 1):
            h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
        h[y][x][0] = matrix[y][x] + max(max(h[j][x]) for j in range(y))

return max(h[H-1][W-1])

经过仔细的检验，可以看出，通过计算它可以消除计算 max(h[H-1][W-1])的 O(W^2 * H^2)运算，使最后的时间复杂度 O(W)。请注意，此优化仅对自底向上方法有效这是因为单元格 max(h[j][x])（其中 O(W * H^2)）应该已经用自底向上的方法访问过了在下面的代码中， (x, j)存储在 j < y中。
python 3中自底向上算法的完整优化版本（包括给定的示例矩阵作为输入和输入矩阵的行反转）：

matrix = [[5, -2, -1, 5, 3, -99, 4, 0],
[5, -2, -1, -3, 3, -99, 2, -3],
[-98, -98, -98, -98, -98, -98, -98, -98],
[-99, -99, -99, -99, -99, -99, -99, -99],
[5, 0, -3, 5, -1, 7, -2, 2],
[1, 2, 7, 0, 0, 1, -1, -1]]

H = len(matrix)
W = len(matrix[0])

for row in matrix:
    row.reverse()

h = [[[0] * (W + 1) for i in range(W)] for j in range(H)]

h[0][0][0] = matrix[0][0]
h[0][0][W] = h[0][0][0]

for x in range(1, W):
    h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x
    h[0][x][W] = h[0][x][x]

for y in range(1, H):
    h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in range(y))
    h[y][0][W] = h[y][0][0]

for y in range(1, H):
    for x in range(1, W):
        h[y][x][0] = matrix[y][x] + max(h[j][x][W] for j in range(y))
        h[y][x][W] = h[y][x][0]
        for r in range(1, x + 1):
            h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
            h[y][x][W] = max(h[y][x][W], h[y][x][r])

print(h[H-1][W-1][W])