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

So I have a n by n grid with 0 at the top left, grid[0][0] marking the start position, and a 0 at the bottom right, grid[n-1][n-1] marking the end position.

The rest of the grid is filled with random positive integers.

My goal is to return the sum from the maximum sum path, from start to end.

I can move down one cell or move right one cell or move diagonally down one cell to the right:

grid[i][j] -> grid[i 1][j] moving down one cell

grid[i][j] -> grid[i][j 1] moving right one cell

grid[i][j] -> grid[i 1][j 1] moving diagonally right down one cell

A restriction is that I cannot immediately move right after moving down or immediately move down after moving right. Essentially I can't make a 90 degrees turn.

Example of not allowed movements:

grid[i][j] -> grid[i 1][j] -> grid[i 1][j 1]

grid[i][j] -> grid[i][j 1] -> grid[i 1][j 1]

grid[i][j] -> grid[i 1][j 1] -> grid[i 2][j 1] -> grid[i 2][j 2]

Example of allowed movements:

grid[i][j] -> grid[i 1][j 1] -> grid[i 2][j 1]

grid[i][j] -> grid[i 1][j] - > grid[i 2][j]

grid[i][j] -> grid[i 1][j 1] -> grid[i 2][j 2]

Example of problem:

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

For this grid the path should be 0->100->200->40->0 which has max sum of 340.

I'm not sure on how to approach this problem as I just started learning dynamic programming. Can anyone help me with defining the recurrence to this problem. I was thinking the base case can be

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

CodePudding user response：

The usual max path sum problem has a 2D DP solution, but since we need to track an additional property here, let's try 3D DP.

Let us assign numbers to the types of turns:

right = 0
diagonal = 1
down = 2

Defined the solution state as dp[i][j][x], which denotes the maximum value till cell [i,j] if turn of type x was used to arrive at [i,j]
You can arrive at [i,j] from:
a. [i, j-1] using a right turn (to determine value of dp[i][j][0])
b. [i-1,j-1] using a diagonal turn (to determine value of dp[i][j][1])
c. [i-1,j] using a down turn (to determine value of dp[i][j][2])
Lastly, while you're computing the value at cell [i,j] for a given turn type x, make sure that the value you pick for the previous cell in the path doesn't use a conflicting turn.

These hints should be enough to set you on the solution path to figure out the recurrence relation.