I don't know whether my solution is better or worse (or even same), just let me describe.
At least mathematically it's simple to calculate all those tilinigs. For k>=1 call tiling to be strongly k-divided
, if it consists of two subtilings, one of them covers 2x[1...k] and rest covers 2x[k+1...N], and there is no l<k with same property within considered tiling. Moreover call first subtiling (which covers 2x[1...k] )
to be fundamental
for strongly k-dividing
Notice that for k<=2 there are exactly one fundamental
__ - for k=1
|| - for k=2
For rest k>=3 there are exactly two fundamental ones:
for k=4 e.g. (stupid padding, cannot show better)
It remains to notice that each
tiling is strongly k-divided for some
k. If F(n) - number of tilings for 2x[1...n] then last sentence leads to formula:
F(N)=F(N-1)+F(N-2)+ 2*sum(F(k), k=1..N-3)
If G(n)=sum(F(k), k=1..N) then
so algorithm could be done in O(1) memory and O(N) time without any dynamic programming stuff.