> 首先，无论任何一种方案，最左边的要么是一根竖的，要么是两根横的，要么是一个方的，对吧？所以：
> 当是一根竖时剩下的方案数是OPT[i-1]
> 当是两根横时剩下的方案数是OPT[i-2]
> 当是一个方时剩下的方案数是OPT[i-2]
> 故OPT[i]=OPT[i-1]+2*OPT[i-2]
> 转化为二阶齐次常系数线性方程为：
> f(n-2)-f(n-1)-2f(n-2)=0
> 其特征方程是：
> x^2-x-2=0
> 解得特征方程的根式:x=-1 或 x=2
> 故得
> f(n)=a*(-1)^n+b*2^n
> 将f(0)=1,f(1)=1的值代入，解得f(n)=1/3*(-1)^n+2/3*2^n
> 可简化为：
> if(n%2==0)
> opt[n]=(2^(n+1)+1)/3
> else
> opt[n]=(2^(n+1)-1)/3
> 最郁闷的是。。用double精度不够，非得要用高精度，我还没找到一本关于高精度的教材来看呢，郁闷死了。。。。所以写不出代码。。。晕。。。

• Re:我是这样推的。。 (27) tanjing 2010-08-27 20:01:06