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

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

在上面的代码中，最差的时间复杂度是什么？我知道每个函数最多会调用一次其他函数，但是我不清楚时间复杂度的计算方法。

最佳答案

备忘录是这里的关键。通常，这将呈指数增长，但是由于如果先前在memo中计算了结果，则从不执行其他递归步骤，因此在最坏的情况下，结果会减少为memo中的元素数。即 O(101 x 101)

关于c++ - 递归的最坏情况时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42624862/