Solution is not fully elaborated

Tags: #<Tag:0x00007f2426840c50> #<Tag:0x00007f2426840b10>


Even though we calculate the value of memo[r][c] only once, But still we call findMinPath(V,r,c) more than once. So it should have been taken care while calculating the time complexity.

For eg.
10 01
20 11 11 02
30 21 21 12 12 03
31 22 22 13

This should be the ideal call tree for a 33 matrix.
and hence the complexity should not be R

    10 01 
 20 11 11 02

I agree with the tree but we are are memoizing it before returning. There are over-lapping sub problems which will be returned from the table instead of recursively going for the sub-problem again. This is the case of dynamic programming (DP). Hence the complexity is not exponential and order of r*c.