PROBLEM LINK: ZIO 2009 Problem 2
Editorialist: Rohit Mazumder
PROBLEM:
In a N x N square grid, find the maximum sum path from any of the squares to the edge of the grid. In each turn, we can move to a square to the right, or to a square down.
EXPLANATION:
Let a(m, n) denote the value at the square (m, n) in the grid.
Let f(m, n) denote the maximum score we can obtain if we start at the square (m, n) in the grid till we cross a boundary of the grid.
So, the question essentially asks us to find max{f(m,n)} for 1<=m<=N, 1<=n<=N.
From a square if we move to the square on its right, then the maximum score we can get is = a(m,n) + f(m,n+1).
Similarly, on moving down, maximum score obtainable = a(m,n) + f(m+1,n)
Now, from a square on the grid we would love to move to a square which will enhance my score the most.
That is to say,
f(m, n) = max{ a(m, n)+f(m+1, n), a(m, n)+f(m, n+1)}
Or, f(m, n) = a(m, n) + max{ f(m+1, n), f(m, n+1)}
where,
f(m+1, n) denotes the maximum score we can obtain if we move the token to the bottom of the current square.
f(m, n+1) denotes the maximum score we can obtain if we move the token to the right of the current square.
a(m,n) denotes the value of the current square which is added to our score.
Base Cases and Edge Cases :
-
If we start at the rightmost and bottom-most square, i.e, m = M and n = N, then the total score we can obtain is a(M,N) as there is no other square left to shift our token too.
So, f(m,n) = a(m,n) ; for m = M and n = N -
If we start from a square situated on the right-most column, i.e, 1<=m<=M-1 and n = N,
Then we can shift the token to the square below it, or end the game by moving the token outside the right boundary.
So, f(m,n) = max{a(m,n), a(m,n)+f(m+1,n)}
or, f(m,n) = a(m,n) + max{0, f(m+1,n)} ; for 1 <= m <= M-1 and n = N -
If we start from a square situated on the bottom-most row, i.e, m=M and 1<=n <= N-1,
Then we can shift the token to the square to the right of it, or end the game by moving the token outside the lowermost boundary.
So, f(m,n) = max{a(m,n), a(m,n)+f(m,n+1)}
or, f(m,n) = a(m,n) + max{0, f(m,n+1)} ; for m = M and 1 <= n <= N-1
Combining all cases, the final recurrence for the problem,
f(m, n) = a(m, n) ; m=M, n=N
f(m, n) = a(m, n) + max{0, f(m+1, n)} ; for 1<=m<=M-1 and n = N
f(m, n) = a(m, n) + max{0, f(m, n+1)} ; for m=M and 1<=n <= N-1
f(m, n) = a(m, n) + max{f(m+1, n) + f(m, n+1)} ; otherwise
The answer to our problem is max{ f(m, n) ; 1<=m<=M, 1<=n<=N}
Solving the given example :
To solve, we solve the recurrence derived using a dp-table. We fill the table from bottom to top, as demonstrated below.
Step 1: We know that f(5,5) = a(5,5) = -9 (According to condition 1 of recurrence)
Step 2: Fill the rightmost column from bottom to top using condition 2 of recurrence
| 2 | ||||
| 7 | ||||
| 7 | ||||
| -3 | ||||
| -9 |
Step 3: Fill the bottom-most row from right to left using condition 3 of recurrence
| 2 | ||||
| 7 | ||||
| 7 | ||||
| -3 | ||||
| 8 | 1 | -2 | 4 | -9 |
Step 4: Fill the rest of the cells starting from (M-1, N-1), row-wise from right to left , using condition 4 of recurrence.
| 10 | 11 | 4 | 12 | 2 |
| 11 | 1 | 10 | 1 | 7 |
| 15 | 10 | 2 | 1 | 7 |
| 5 | 12 | 8 | 1 | -3 |
| 8 | 1 | -2 | 4 | -9 |
Step 5: Answer = Maximum value in the table = 15
Subtask 1:
| 23 | 14 | 13 | 12 | 8 |
| 25 | 13 | 16 | 1 | 12 |
| 13 | 29 | 6 | 13 | 6 |
| 23 | 16 | 20 | -2 | 10 |
| 13 | 20 | 4 | 13 | -16 |
Answer = 29
Subtask 2:
| 4 | 7 | 3 | 8 | -2 |
| 8 | 3 | 9 | 3 | 5 |
| 2 | 9 | 4 | 8 | -2 |
| 9 | 3 | 7 | 1 | 5 |
| 2 | 7 | 1 | 6 | -4 |
Answer = 9
Subtask 3:
| 14 | 18 | 12 | 16 | 9 |
| 20 | 13 | 16 | 3 | 13 |
| 13 | 19 | 9 | 8 | 1 |
| 15 | 7 | 14 | 4 | 3 |
| 4 | 13 | 2 | 9 | -2 |
| 8 | -5 | 5 | -4 | 5 |
Answer = 20
