使用动态编程的网格中从左上到右下的最大和路径

Question

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

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

我的目标是从最大和路径返回和，从开始到结束。

我可以向下移动一个单元格，也可以向右移动一个单元，也可以斜向下移动一单元格到右侧：

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

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

网格[i][j]->网格[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。

1. 让我们为转弯类型指定数字：

right = 0
diagonal = 1
down = 2

2. 将溶液状态定义为dp[i][j][x]，表示如果使用类型x的轮次到达[i,j]，则直到单元[i,j]的最大值

3. 您可以从：
   a到达[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]的值(

4. 最后，在计算给定转弯类型x的单元格[i,j]处的值时，请确保为路径中的前一个单元格选择的值不使用冲突转弯。

这些提示应该足以让您了解解决方案路径，以找出重复关系。