c++ - 将此递归函数转换为迭代函数

Question

如何将此递归函数转换为迭代函数？

#include <cmath>

int M(int H, int T){
    if (H == 0) return T;
    if (H + 1 >= T) return pow(2, T) - 1;
    return M(H - 1, T - 1) + M(H, T - 1) + 1;
}

这是一个 3 行代码，但我很难将其转换为迭代函数。因为它有2个变量。而且我对 Stacks 一无所知，所以我无法转换它。

我这样做的目的是提高函数的速度。这个功能太慢了。我想使用 map 来加快速度，但我有 3 个变量 M、H 和 T，所以我不能不使用 map

Answer 1

您可以使用动态规划 - 当 H == 0 和 T == 0 计算 M 并迭代它们时，从下往上开始。这是一个link解释如何对斐波那契数执行此操作，这与您的问题非常相似。