首先，无论任何一种方案，最左边的要么是一根竖的，要么是两根横的，要么是一个方的，对吧？所以：
当是一根竖时剩下的方案数是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:我是这样推的。。 (10) qq312873977 2009-04-24 00:45:22
• Re:我是这样推的。。 (479) tanjing 2010-08-27 19:59:54
  • Re:我是这样推的。。 (27) tanjing 2010-08-27 20:01:06
• Re:我是这样推的。。 (479) W20164340 2018-03-22 13:36:50