REC_CMPL3

What is the worst case time complexity of the following code:

int memo[101][101];
int findMinPath(vector<vector<int> >& V, int r, int c) {
  int R = V.size();
  int C = V[0].size();
  if (r >= R || c >= C) return 100000000; // Infinity
  if (r == R - 1 && c == C - 1) return 0;
  if (memo[r][c] != -1) return memo[r][c];
  memo[r][c] =  V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));
  return memo[r][c];
}

Callsite : 
memset(memo, -1, sizeof(memo));
findMinPath(V, 0, 0);

Assume R = V.size() and C = V[0].size() and V has positive elements

•  O(2^(R + C))
•  O(R*C)
•  O(R + C)
•  O(R*R + C*C)
•  O(R*C*log(R*C))

Good solution:

You can see it this way, For each call to findMinPath you either take constant time to return or before returning set the value of memo[r][c] so that when next time it is called with same r and c it takes constant time. So maximum possible calls to the function with different set of r,c values is equal to all possible combination of (r,c). Now range of r is 0 to R-1 and c is 0 to C-1 so max possible combination are RC. All instructions inside a function take constant time so overall time complexity will be O(RC).

First learn that how Dynamic programming is works with example of Fibonacci Series.
in fibonacci series dp we use this term f[i] = f[i-1] + f[i-2];
this means it create 1D Array of N numbers and fill all value in it by calling fib function recursively.
so for filling after whole array is fill, it just fetch the value from it so it take O(1) time and filling array process take O(N) time.

memo[r][c] =  V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));

In the same Manner here we use memo[r][c] 2D Array and elements are rc so it will take O(rs) time to fill array.