“Optimism is an occupational hazard of programming: feedback is the treatment.” — Kent Beck
Hola lectores! Hope you liked the previous blog where we discussed one of a good foundation building DP problem which focused on finding total number of ways to reach target cell, today we would advance our learning by 1 more step. So, lets start with another new and interesting DP problem which would clear more of your concepts… All the best 👍.
Note — Do give a look at the additional discussion section.
Let’s start with the discussion
Today, we will be solving an medium-level DP problem named Minimum Path Sum from LeetCode. The problem states -“We have a N*M grid and we have to move from the top-left cell (i.e. (0, 0)) to the bottom-most right cell (i.e. (N-1, M-1)); each cell of the grid contains a non-negative number, denoting the cost of passing through that cell. Return the minimum cost you have to spend to complete the journey, 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)) ”
Constraint — 1≤ N, M ≤ 10³.
Let’s start solving
Step 1 — Build a naive recursive solution
Suppose we are at a cell ( i , j ) so according to the direction constraints you can either go to ( i, j+1) or (i+1, j), so next time our sub-problem would be to move from (i, j+1) to (N, M) and to move from (i+1, j) to (N, M). We would solve each of the two sub-problems and add minimum of the either returned values with the current cell value.
Based on this intuition we can easily form the below recurrence:
min_cost(i, j) = cost[i][j] + min ( min_cost(i, j+1), min_cost(i+1, j)
So, by the above recurrence you can easily write your own recursive solution which would look something like —
Time Complexity — O( 2^(n*m)) ( Since at each cell we can move in 2 ways and there are in total n*m cells. In worst case this complexity would go up-to 2¹⁰⁰⁰⁰⁰⁰)
STEP 2 — Memoize the recursive solution
Look at the changing parameters in each function call, they are none other than curr_row and curr_col which indicates current row and current column respectively. So, if we somehow make a memoization table keeping a record of all row, col value we would be done.
So, here is our memoized code —
Time Complexity — O( n*m ) (Since we visited each cell only once)
Additional Discussion
By now, you might have got a clear understanding of how to write a memoized solution from the previous blogs. But have you ever wondered, what values does these memoized table contains and how they are filled.
Let’s explore this today
As written in the above code we started our recursion from cell (0, 0) and moved to (n-1, m-1). The approach we followed was a top-down approach since the value storage part started from cell (n-1, m-1). Look at the below picture to see what I mean by the previous statement.
Now, if we take a look of the above code then from the first base case we can assure that whenever we reach the bottom-most right cell only 1 single value is stored.
Suppose we are at (2, 1) i.e. the cell with cost 8, the code-flow would be like :ans = Cost[2][1] + min( min_cost(2, 2), min_cost(3, 1))at the next step the function min_cost(2, 2) would be called which would return 9 (as per the first base case)followed by the second function call min_cost(3, 1) which would return INT_MAX (as per the second base case)Thus, ans for (2, 1) would be: 8 + min(9, INT_MAX) = 17Hence, in the dp matrix at (2, 1) the value stored would be 17.
Following the same procedure all the values would be filled in the DP matrix starting from the bottom-most right cell. Thus we call this method Top-Down DP.
The DP matrix would look like.
Now, there is one more interesting thing which you can do with the above dp matrix. You can trace the cheapest path.
Step would be:
- Start from bottom-most right cell, we know that we would have reached there either from the immediate left or the cell above it.
- Find the smallest out of the above two from the dp-matrix and then move your pointers to that cell.
- In case you are at the top-most row then all you have to do is to move left until you reach (0, 0). Similarly, if you are at the 0'th column of some row all you have to do is to move up until you reach (0, 0).
Congrats! You made through another DP blog and not-only learnt the minimum cost problem but also understand how DP table fills up and also how to smartly use the DP table to solve extended problems.
Moreover you can also try to print the memoized values from previous blogs to see how DP actually works and looks in practice.
To check you understandings, try to write code for the following practice problems.
- Minimum Path Sum (LeetCode) — The above problem
- Maximum Path Sum — Same as the above problem
- Print the path with maximum sum.
Hope you enjoyed the blog and learnt something new.
P.S. — One of my mentor got this problem in his Microsoft Interview 😉
For any doubts in the above explanation or regarding solutions of any of the mentioned practice problems you can mail me at — ankitpandeycu@gmail.com
Share this blog with your peers if you find it useful.
Hope it helps.
AnkitCode99 here….
