c++ - 递归的最坏情况时间复杂度

Question

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);

在上面的代码中，最坏情况下的时间复杂度是多少？我知道每个函数最多调用一次其他函数，但我不清楚时间复杂度的计算。

Answer 1

内存是这里的关键。通常这会呈指数增长，但由于如果结果先前已在 memo 中计算，则您永远不会执行额外的递归步骤，因此它会减少为 memo 中的元素数，如下所示最坏的情况。即 O( 101 x 101 )