c++ - 为递归函数实现DP

Question

我有以下递归函数:

typedef unsigned long long ull;

ull calc(ull b, ull e)
{
  if (!b) return e;
  if (!e) return b;
  return calc(b - 1, e - 1) + calc(b - 1, e) - calc(b, e - 1);
}

我想用动态规划(即使用存储)来实现它。我试过使用 map<pair<ull, ull>, ull>但它也太慢了。我无法使用数组实现它 O(1)也是。

我想找到一个解决方案，让这个函数快速解决大 b, e

Answer 1

制作一个表格 b/e 并逐个单元格地填充它。这是具有空间和时间复杂度 O(MaxB*MaxE) 的 DP。

Ante 在评论中提出的建议可能会降低空间复杂性 - 仅存储两个需要的行或列。

0 1 2 3 4 5
1 0 3 . . .
2 . . . . .
3 . . . . .
4 . . . . .