PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Given a grid of size N*N, some of whose cells are impassable. You are in the top left cell and want to reach the bottom right cell, moving only one step to the right or downwards, in each move. Each cell also has a certain number of coins you collect on passing through it.
You may choose a sequence of at most K adjacent cells and make them passable. Determine if it is possible to reach the bottom right cell, and the maximum amount of coins you can collect.
EXPLANATION:
Note: We use 0 based row and column indexing in the editorial.
When K=0, the problem is a slight modification of a classical grid DP problem. We build our solution directly atop it (readers are requested to get acquainted with the DP solution of the above problem).
Intuition for the DP states
Let’s try visualising our path through the grid. If we denoted passable cells as P and the cells made passable using the special ability as S, our path would look something like:
Small point of contention - we can make the number of S exactly equal to K by using the special ability continuously on the adjacent P cells (while still keeping the path valid).
Therefore, apart from tracking our current position, we also need to keep count of our position w.r.t. the special ability. More precisely, we keep another state k, such that:
- k=0 implies we are in the first section of the above path (that is, we haven’t yet used the special ability).
- 1\le k\le K implies we are in the middle section (and have used the special ability on the last k cells).
- k = K+1 implies we are in the last section (having used our special ability completely).
Let dp[i][j][k] be the maximum number of coins we can collect if we move till cell (i,j) and have already made k adjacent cells on our path passable. Initially, all values are -INF.
The only base case - dp[0][0][0] = A_{i,j} is obvious.
The transition states of the DP are (out-of-bounds states are -INF):
-
dp[i][j][k] = \max(dp[i-1][j][k-1], dp[i][j-1][k-1])+A_{i,j}
We use the special ability and make cell (i,j) passable, irrespective of whether it is already passable or not.
-
dp[i][j][0] = \max(dp[i-1][j][0], dp[i][j-1][0])+A_{i,j}
Only when cell (i,j) is passable by default. We walk through the cell normally, without having travelled on any special cells before.
-
dp[i][j][K+1] = \max(dp[i-1][j][K], dp[i-1][j][K+1], dp[i][j-1][K], dp[i][j-1][K+1])+A_{i,j}
Only when cell (i,j) is passable by default. We walk through the cell normally, having already used the special ability on cells before this cell.
The final answer is then \max(dp[N-1][N-1][0], dp[N-1][N-1][1], \dots) or -1 if the answer is negative (implying no valid path exists).
TIME COMPLEXITY:
Since computing each state of the DP takes O(1), and computing the final answer takes O(K), the total time to compute the DP table is:
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters