递归函数到迭代

Question

给出以下函数：

    T(n, 0) = n, n >= 0,
    T(0, k) = k, k >= 0,
    T(n, k) = T(n - 1, k - 1) + T(n, k - 1) + 1, n > 0 and k > 0

我想要实现的是将其转换为迭代版本。我已经尝试绘制递归树来注意一些依赖关系，但我仍然无法弄清楚。

你有什么建议吗？

Answer 1

要计算 T(n, k)，您可以使用以下迭代方法：

• S(i)表示T(0,i)到T(n,i)的向量
• 用零初始化你的状态向量 S(0)
• 对于 i=1 到 k
• 使用 S(i-1) 计算 S(i)
• 结束
• 你的结果是 S(i) 的最后一个元素

请注意，您只需要最近的 S(i)，为了提高内存效率，您可以只存储它。