Bottom up approach has to consider many corner cases


#1

Why doesn’t top down approach work here ?


#2

not at all, its quite easy


#3

Maintain 2D array with M+1, N+1 dimensions.
[2][0] … [M+1][0] = -INF
[0][2] … [0][N+1] = -INF
[0][0] = [0][1] = [1][0] = 0

No corner case needs to be handled.


#4

If you solve this problem with top down, then optimal sub-substructute property of this problem would break for DP. Only bottom up approach devises substructure property.
This problem is not same in reverse. Here, ordering/direction matters.