title: Explanation and time/space complexity of tri tiling
body: <p>I am having problems understanding what exactly is going on in the solve function below. I see what it does, however it still is unclear to me - I cannot visualize it, or just get myself to understand it. Can someone explain it?</p>
  <p>Original problem statement (<a href="http://uva.onlinejudge.org/index.php?option=onlinejudge&amp;page=show_problem&amp;problem=1859" rel="nofollow noreferrer">link</a>):</p>
  <blockquote>
  <p>In how many ways can you tile a 3xn rectangle with 2x1 dominoes?</p>
  <p>Here is a sample tiling of a 3x12 rectangle.</p>
  <p><img src="https://i.stack.imgur.com/krTp3.gif" alt="" /></p>
  </blockquote>
  <p>Code (taken from <a href="http://f0rth3r3c0rd.wordpress.com/2011/09/05/uva-10918-tri-tiling/" rel="nofollow noreferrer">here</a>):</p>
  <pre><code>#include &lt;stdio.h&gt;
  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&lt;=n;i+=2)
              res+=2*solve(n-i);
          return dp[n]=res;
      }
  }
  int main()
  {
      int i;
      for(i=0;i&lt;32;i+=2)
          dp[i]=-1;
      for(i=1;i&lt;32;i+=2)
          dp[i]=0;
      dp[0]=1;
      scanf(&quot;%d&quot;,&amp;i);
      while(i!=-1)
      {
          printf(&quot;%d\n&quot;,solve(i));
          scanf(&quot;%d&quot;,&amp;i);
      }
      return 0;
  }
  </code></pre>
  <p>Another thing is, what could be the time and space complexity of this algorithm? Since it is a recursive function, it might be <code>O(log N)</code>, but I am not sure about that either.</p>