为递归函数实现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);
}

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

我想找到一个解决方案,以便此函数可以快速解决大b, es问题.

Answer 1

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

Ante的评论建议可以减少空间复杂性 - 只存储两个所需的行或列.

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