DP is easy — Part-8

5 min readNov 3, 2020

“Simplicity is the soul of efficiency.” — Austin Freeman

Hey readers! Hope you all are safe and fit during this pandemic situation. On this positive note let’s begin with the 8'th blog of this DP-series.

In the previous blog, we discussed Min-Cost Path problem, where we saw how to find the cheapest path from the top-most left cell to the bottom-most right cell of a grid. Today we will be solving a slight tougher version of the same problem, so, lets begin with that without any further delay.

NOTE: If you have not read the previous blog, I would highly recommend you to go through that as it would improve your thought process and understanding for this problem.

Let’s start with the discussion

Today we will be solving a good DP problem from AtCoder Beginner Contest_#175. This was the E-problem in the problem-set. The problem statement was something like — “ We have a R*C grid and we have to move from the top-most left cell (i.e. (0, 0)) to the bottom-most right cell (i.e. (R-1, C-1)); only K cells of the grid coin of some value-v, while others do not contain any coin at-all. Return the maximum coin sum you can calculate on your way to (R-1, C-1), provided that you can pick at-most 3 coins from any row. At each step you can either move Right (i.e. from (i, j ) → (i, j+1)) or move Down (i.e. from (i, j) → (i+1, j)) moreover at each cell you can either pick the coin(if present) or do not pick anything.” ( You can refer to the original problem statement here. )

Constraints — 1≤ R,C ≤ 3000; 1≤ K ≤min(2×10⁵,R×C); 1≤ v ≤10⁹

Let’s start solving

Step 1 — Build a naive recursive solution

Suppose we are at cell ( i, j ) and currently we have taken ‘c’ coins from this row. So, according to the direction constraints we can either go to ( i+1, j ) or ( i, j+1 ). Let’s break-down our problem into 2 parts :

We are not picking anything from the current cell irrespective of the presence of coin

This means, if we are at ( i, j ) with ‘c’ coins from the current row.

So, we can proceed further in either of the following 2 ways :

move to next row within the same column and reset the coin count to 0, i.e. move from state ( i, j, c ) to ( i+1, j, 0 ).
Or, move to next column within the same row without changing the coin count ( because we are considering no-pick condition ), i.e. move from state ( i, j, c ) to ( i, j+1, c).

From either of the two choices we will select the one which gives maximum coin value.

2. If out coin count for current row is less than 3 and the current cell contains a coin

This means we are at ( i, j ) with ‘c’ coins from the current row. We can again proceed further with either of the following 2 ways :

pick the coin, move to the next row within the same column and reset the coin count to 0, i.e. move from state ( i, j, c ) to ( i+1, j, 0 ) along-with adding the value of the picked coin in our calculation.
pick the coin, move to the next column within the same row and increase the coin count by 1, i.e. move from state ( i, j, c) to ( i, j+1, c+1 ) along-with adding the value of the picked coin in our calculation.

From the above 2 choices we again need the maximum .

Finally, we return the maximum value obtained after considering case-1 and case-2.

If you give a though on the problem you can easily conclude that the both the above mentioned points are the only possibilities for any cell ( i, j ).

The problem has only 1 very simple base case and that is : moving to a cell outside the grid, since to ignore this we can simply return 0 if such situation arises.

So, here is the recursive code from the above discussion —

Sometimes the problem statements itself gives you the solution. This is one of the case.

Time Complexity — Exponential ( Since at each cell we can move in 2 ways and there are in total R*C cells, moreover in worst case of all cells contain coins it would be R*C*3. Hence worst case complexity would be extremely high 2³⁰⁰⁰⁰⁰⁰)

STEP 2 — Memoize the recursive solution

From the above recursive code it is clearly evident that the changing parameters are nothing but curr_row, curr_col, coin_count. If we somehow keep a track for all of them we would be done.

The values of curr_row, curr_col would be between 1 to 3000, and that of coin count would be between 0 to 3. So, we can build a 3-dimensional DP table of dimension-3005 x 3005 x 4 (3005, is consider in-place of 3000 to avoid runtime error (if arises) in any critical corner-case).

So, all we need to do is, before returning the ans value, just assign that in the respective DP-table index.

Here is the memoized code, after modification on our recursive code: