1

我有以下递归函数：

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

我想用动态编程（即使用存储）来实现它。我曾尝试使用 amap<pair<ull, ull>, ull>但它也太慢了。我也无法使用数组来实现它O(1)。

我想找到一个解决方案，以便此函数快速解决大b, es。

4

4 回答 4

5

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

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

0 1 2 3 4 5
1 0 3 . . .
2 . . . . .
3 . . . . .
4 . . . . .
于 2012-07-03T07:20:36.793 回答
2

如果自下而上的表示是您想要的，那么这会很好。

如 MBo 所示填写表格

这可以这样做：

for e from 0 to n:
  DP[0][e] = e
for b from 0 to n:
  DP[b][0] = b
for i from 1 to n:
   for j from 1 to n:
      DP[i][j] = DP[i-1][j-1] + DP[i-1][j] - DP[i][j-1]

现在你对任何 b,e 的回答只是 DP[b][e]

于 2012-07-03T07:25:06.010 回答
2

您可能想看看最近发布的关于通用自动记忆的博客。作者讨论了各种数据结构，例如等。警告：使用大量模板代码。std::mapstd::unordered_map

于 2012-07-03T07:21:04.933 回答
1

您可以使用二维数组在 O(n^2) 中实现（假设 n 作为 b 和 e 的最大值数）。i,j 的每个当前值将取决于 i-1,j 和 i-1,j-1 和 i,j-1 处的值。确保处理 i=0、j=0 的情况。

于 2012-07-03T07:21:16.853 回答