Tri tiling的說明和時間/空間複雜度

Question

我在理解下面的求解函數到底發生了什麼問題。我明白它的作用，但它仍然不清楚 - 我無法想象它，或者只是讓自己理解它。有人可以解釋嗎？

原始問題陳述（link）：

在多少種方法你拼貼的3XN矩形2×多米諾骨牌？

這是一個3x12矩形的示例平鋪。

代碼（從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 ）。在進行了一定大小的遞歸調用之後，任何未來的相同大小的遞歸調用都會在時間O（1）中運行。這是由於在dp表中使用記憶。這意味着我們可以通過總結所有可能的遞歸調用計算總運行時間，即填寫表格所需的時間。

在大小爲n的調用中，完成了O（n）工作來填充數組。你可以通過for循環來看這個，從4開始，並且在每個點做O（1）工作的時候計數到2。由於遞歸調用的大小爲0,1,2，...，n，所以我們有O（n）個調用，每個調用O（n），總共有O個工作。

希望這會有所幫助！