降低递归斐波那契类函数在 C++ 中的时间复杂度

Question

我一直在尝试用 C++ 编写解决问题的代码。

这只能使用递归来解决 取模 10000000007 不是代码耗时较长的问题 with/without 它

问题：戴维斯喜欢一次爬楼梯 1、2 或 3 步。

给定 n 个楼梯各自的高度，找出并打印他可以爬上每个楼梯的方式数，模 10^10 + 7

例子对于 n=5

楼梯有 5 级台阶。戴维斯可以按以下步骤顺序进行操作：

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1

2 1 1 1

1 2 2

2 2 1

2 1 2

1 1 3

1 3 1

3 1 1

2 3

3 2

他可以采取这 5 个步骤的 13 种可能方式和 13 模 10000000007 = 13

到目前为止我使用递归的解决方案：

int ways(int n) {
    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;
    return (ways(n-3)+ways(n-2)+ways(n-1))%10000000007;
}

该代码运行完美，但在大型计算上花费的时间太长。如果有优化它的方法，请分享。解决方案越简单越好。谢谢

Answer 1

您可以开始添加记忆，以避免大多数递归调用。

long long ways(long long n)
{
    // Memoization requires to store the previously calculated values.
    static std::map<long long, long long> mem{
        {1, 1}, {2, 2}, {3, 4}
    };

    // I'm using std::map, but I don't want to use operator[], nor find...
    // https://en.cppreference.com/w/cpp/container/map/operator_at
    // https://en.cppreference.com/w/cpp/container/map/find
    // https://en.cppreference.com/w/cpp/container/map/lower_bound
    auto it = mem.lower_bound(n);

    // If it has already been calculated, return the stored value.
    if ( it != mem.cend() and it->first == n )
        return it->second;

    // Otherwise evaluate the new value (recursively) and store it
    // Note that I can use the iterator as an hint for the insertion.
    // https://en.cppreference.com/w/cpp/container/map/emplace_hint
    return mem.emplace_hint(
        it, n,
        (ways(n-3) + ways(n-2) + ways(n-1)) % 10000000007
    )->second;
}

如果这还不够，您将不得不寻找一些数学技巧，或者完全避免递归并使用简单的循环。

Answer 2

该算法计算自定义 Tribonacci 序列 模数 10000000007。这可以在 O(log n) 时间和 O(1) space 基于序列的 矩阵表示 ，例如 Fibonacci。有关详细信息，请参阅 this post and this answer。

这种方法对于大输入非常快（比使用记忆快得多）并且非常节省内存。

但是，有一个问题：实现需要计算两个 64 位整数与 64 位整数的模相乘（除非模数可以容纳 32 位整数）。大多数平台不支持 128 位整数，但可以使用 boost::multiprecision。有关详细信息，请参阅 this post。

这是一个实现：

int64_t int128_mulMod(int64_t a, int64_t b, int64_t mod)
{
    return int64_t((int128_t(a) * int128_t(b)) % int128_t(mod));
}

// Compute the matrix multiplication of a * b and put the result in a
void matMulMod(int64_t a[3][3], int64_t b[3][3], int64_t mod)
{
    int64_t res[3][3] = {};

    for(int i=0 ; i<3 ; ++i)
        for(int j=0 ; j<3 ; ++j)
            for(int k=0 ; k<3 ; ++k)
                res[i][j] += int128_mulMod(a[i][k], b[k][j], mod);

    for(int i=0 ; i<3 ; ++i)
        for(int j=0 ; j<3 ; ++j)
            a[i][j] = res[i][j];
}

// Compute the matrix exponentiation a^n and put the result in a
void matPowMod(int64_t a[3][3], int64_t n, int64_t mod)
{
    if(n == 0 || n == 1)
        return;

    int64_t m[3][3] = {{ 1, 1, 1 },
                       { 1, 0, 0 },
                       { 0, 1, 0 }};

    // Use recursion to square the matrix efficiently
    matPowMod(a, n / 2, mod);

    // Square the matrix
    matMulMod(a, a, mod);

    // Remainder case
    if(n % 2)
        matMulMod(a, m, mod);

    // Apply the modulus on each term to prevent overflows
    for(int i=0 ; i<3 ; ++i)
        for(int j=0 ; j<3 ; ++j)
            a[i][j] %= mod;
}

int64_t ways_fast(int64_t n)
{
    int64_t a[3][3] = {{ 1, 1, 1 },
                       { 1, 0, 0 },
                       { 0, 1, 0 }};

    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;

    matPowMod(a, n, 10000000007ll);
    return a[0][0]; // Result of the Tribonacci sequence
}

例如，在我的机器上，ways_fast(30'000) 比计算@Bob__ 提供的基于记忆的方法快 100 倍。此外，记忆算法在计算 ways(60'000) 时崩溃，而 ways_fast(200'000) 正常工作。

更多信息请阅读：

降低递归斐波那契类函数在 C++ 中的时间复杂度

Reducing the time complexity of recursive Fibonacci like function in c++

c++

math

optimization

time-complexity