c++ - 此代码 O(R*C) 的最坏时间情况如何？

Question

我在 InterviewBit 上遇到了这个问题:

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

假设 R = V.size() 和 C = V[0].size() 和 V 有正元素

代码不会创建一个采用 O(2^(m+n)) 的二叉树函数调用，因为每个函数调用都会调用另外两个函数吗？

Answer 1

该算法使用了一种称为 dynamic programming 的技术.其本质是将中间结果存储在查找表中，并找到作为部分解决方案组合的整体解决方案。

在这种特殊情况下，您可以看到每次调用 findMinPath要么是具有恒定复杂性的叶调用(非递归)，要么在 memo 中至少输入一个条目变成非负数。很容易看出，如果 memo 中的所有条目是非负的，函数永远不会递归。由于 memo 中只有 R × C 元素，这是整体复杂度的上限。

也就是说，实现起来相当笨拙。为什么为 memo 使用全局变量并依赖它被初始化为 -1由来电者？此外，使用 memset写一个整数数组只适用于一些所有字节都相同的整数，这对整数布局做出了不可移植的假设。最后，如果 R 或 C 超过魔术值 101，则存在缓冲区溢出漏洞。因此，如果你想迂腐，实际复杂度是恒定的。