10918:Tri Tiling

問題文
http://uva.onlinejudge.org/external/109/10918.html

2×1のタイルを使って3×nの長方形を作るときの作り方が何通りあるかを求めよ。

f[横の長さn]:=3×nの長方形の作り方の総和
g[横の長さn]:=3×nの長方形から隅を一つ消した形の作り方の総和

.......   AA......   AA......   A.......
....... = BB...... + B....... + A.......
.......   CC......   B.......   BB......
 f[ i ] = f[ i-2 ] + g[ i-1 ] + g[ i-1 ]

 ......    .......    AA.....
....... = A....... + BB......
.......   A.......   CC......
 g[ i ] = f[ i-1 ] + g[ i-2 ]

#include<iostream>
 
using namespace std;
 
int main(void){
 
    int f[40],g[40],n;
     
    f[0]=g[1]=1;
    f[1]=g[0]=0;
     
    for(int i=2;i<40;i++){
        g[i]=f[i-1]+g[i-2];
        f[i]=f[i-2]+g[i-1]*2;
    }
     
    while(cin >> n,~n)cout << f[n] << endl;
     
    return 0;
}