Editorial : Earn to Advance

Assume there’s a pandemic incoming. You are short on food, but you do not know how many days the pandemic might last. Also, the price of food fluctuates everyday. Would you buy all the food on Day 0 of the pandemic? If so, what if the food gets cheaper in the next few days? If not, what if the food gets so expensive that you aren’t able to buy anymore food in future?

What if you had a time machine? Now, it’s easy to see that it’s not optimal to stock up on food. Every day, you should use the time machine to go to the past day with the cheapest food and buy the minimal quantity of food that you will eat that day. Of course, there will be some left over food that you can eat the next day. For example, the supermarket only sells a full cake, while you might eat just half of it in a single day. But during your purchase, you should never think about left over food. But what if there are 2 days in the past with the same lowest cost of cake. Which one should you choose? You should choose the one that gives you the maximum leftover food for the future days.

In this problem, p[i][j] represents the amount of money earned, while r[i][j]and d[i][j] is the amount of money spent. Whenever you need to earn money, you can simply go back to the past with the maximum p[i][j], spend 1 action and earn the best possible amount.

Let

dp[i][j][max_p] = (action, left_over_money)

Note that max_p doesn’t mean that we earned max_p amount of money. It just means that if we go back to the past, the best day to earn money would give you a profit of max_p.

Then, it’s clear that our goal is to never maximize the left over money. Instead, we should always minimize the number of actions. If you are at a cell (i, j), and going right gives you a bigger max_p but requires you to take more action, while going down gives you a smaller max_p but requires you to take less action, which one would you choose?

It’s a trick question. You should choose both of them. Note that our goal is to never maximize max_p. It is a parameter in the DP, not the DP value.

How does this DP cover all scenarios? Because when you arrive at a cell, max_p has to be equal to one element of the matrix. Hence, if we replace max_p with the index of the element, then we would’ve evaluated all possibilities.