PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
After reading the problem, you may feel its a Dynamic Programming (DP) problem. Yes, it is… but there are few more things to consider. Po moves down and Mantis moves left and they need to maximize the choco chips they collect. You can run a dp normally, but the problem with this is, you also need to remember the cells visited by Po and do not add that when Mantis visits it again. That doesn’t sound good. If you observe carefully, Po should always move down and Mantis should always move left, and they both should reach (N,1). Both of them can not cross the diagonal ! So, they can only meet on the diagonal. We can as well try all possible cells at which both of them reach the diagonal ( refer setters solution ), or you can do a O(n) method going from bottom-top on the diagonal ( refer testers solution ). Complexity is O(n^2).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.