c - tri tiling的解释和时间/空间复杂度

Question

我无法理解下面的 solve 函数到底发生了什么。我看到它做了什么，但我仍然不清楚 - 我无法想象它，或者只是让自己理解它。谁能解释一下？

原始问题陈述(link):

In how many ways can you tile a 3xn rectangle with 2x1 dominoes?

Here is a sample tiling of a 3x12 rectangle.

代码(取自 here ):

#include <stdio.h>
int dp[32];
int solve(int n)
{
    if(dp[n]!=-1)
        return dp[n];
    else
    {
        int i;
        int res = 3*solve(n-2);
        for(i=4;i<=n;i+=2)
            res+=2*solve(n-i);
        return dp[n]=res;
    }
}
int main()
{
    int i;
    for(i=0;i<32;i+=2)
        dp[i]=-1;
    for(i=1;i<32;i+=2)
        dp[i]=0;
    dp[0]=1;
    scanf("%d",&i);
    while(i!=-1)
    {
        printf("%d\n",solve(i));
        scanf("%d",&i);
    }
    return 0;
}

另一件事是，这个算法的时间和空间复杂度是多少？由于它是一个递归函数，它可能是 O(log N)，但我也不确定。

Answer 1

从技术上讲，运行时间是 O(1)，因为输入的大小有上限(具体来说，32)。但是让我们暂时假设问题大小最多不是 32，然后考虑一下这个问题。在这种情况下，运行时间为 O(n²)。在进行了一定规模的递归调用之后，任何 future 相同规模的递归调用都会在时间 O(1) 中运行。这是由于在 dp 表中使用了内存。这意味着我们可以计算总运行时间，方法是对所有可能进行的递归调用求和，以填充 dp 表所需的时间量。

在大小为 n 的调用中，完成了 O(n) 的工作来填充数组。您可以通过 for 循环看到这一点，该循环从 4 开始并以二为单位计数到 n，在每个点执行 O(1) 工作。由于递归调用的大小为 0、1、2、...、n，因此我们有 O(n) 次调用执行 O(n) 次工作，每次总计 O(n²)工作。

希望这对您有所帮助!