When I first came across this problem, I was stuck. I could not write the solution in 20 minutus. I wondered whether it should be solved by dynamic programming, or whether it should be done by 2D state variable. Or it should be done by greedy algorithm? When I checked out the solution, I found…