Can be solved without using DP in an iterative way


Hi, instead of using DP and additional recursive stack memory we can use normal matrix traversal logic in 4 directions.


each of the above dimensions require 2 traversals at max as a future/ahead 1 may lead to increment for a previous 1/0…so at most we traverse an element twice.
So each dimension takes (m* n)*2.

Therefore 4 dimension traversal takes 4( (m * n) * 2) ===8 *(m * n).

Happy Coding!


Can you please share your code?


But this is a really cumbersome way.