使用动态规划在网格中从左上角到右下角的最大和路径

Question

所以我有一个 n 乘 n 的网格，其中 0 在左上角，grid[0][0] 标记开始位置，0 在右下角，grid[n-1][n-1]标记结束位置。

网格的其余部分用随机正整数填充。

我的目标是return从最大和路径求和，从头到尾。

我可以向下移动一个单元格或向右移动一个单元格或向右斜向下移动一个单元格:

grid[i][j] -> grid[i+1][j] 向下移动一个单元格

grid[i][j] -> grid[i][j+1] 向右移动一个单元格

grid[i][j] -> grid[i+1][j+1] 沿对角线向右移动一个单元格

一个限制是我不能下移后立即右移，也不能右移后立即下移。基本上我不能转90度。

不允许移动的示例：

网格[i][j] -> 网格[i+1][j] -> 网格[i+1][j+1]

网格[i][j] -> 网格[i][j+1] -> 网格[i+1][j+1]

网格[i][j] -> 网格[i+1][j+1] -> 网格[i+2][j+1] -> 网格[i+2][j+2] ]

允许的移动示例：

网格[i][j] -> 网格[i+1][j+1] -> 网格[i+2][j+1]

网格[i][j] -> 网格[i+1][j] -> 网格[i+2][j]

网格[i][j] -> 网格[i+1][j+1] -> 网格[i+2][j+2]

问题示例：

[0, 100, 10, 20]
[20, 100, 200, 70]
[10, 10, 40, 30]
[1000, 10, 10, 0]

对于此网格，路径应为 0->100->200->40->0，最大总和为 340。

刚开始学习动态规划时，我不确定如何解决这个问题。谁能帮我定义这个问题的复发。我在想基本情况可以是

if grid[row][col] == 0:
    return 0

Answer 1

通常的最大路径和问题有一个 2D DP 解决方案，但由于我们需要在这里跟踪一个额外的属性，让我们尝试 3D DP。

right = 0
diagonal = 1
down = 2

将求解状态定义为dp[i][j][x]，如果使用x类型的轮次得到[=12]，则表示单元格[i,j]之前的最大值=]
您可以从以下地点到达 [i,j]：
一种。 [i, j-1] 使用右转（确定 dp[i][j][0] 的值）
b. [i-1,j-1] 使用对角线转弯（确定 dp[i][j][1] 的值）
C。 [i-1,j] 使用向下转向（以确定 dp[i][j][2] 的值）
最后，当您计算给定转弯类型 x 单元格 [i,j] 处的值时，请确保您为路径不使用冲突转弯。

这些提示应该足以让您走上解决递推关系的道路。

Maximum sum path from top left to bottom right in a grid using dynamic programming