状态：d[i]代表n=i时的方案数。
状态转移方程：d[i]=d[i-2]+2*(d[i-2]+d[i-4]+…+d[0])
i只会为偶数，奇数情况不存在，d[0]=1
找状态转移方程的时候画图更好理解。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int d[50]; int main() { int n; d[0]=1; d[2]=3; int sum=d[0]+d[2]; for(int i=4;i<=30;i+=2) { d[i]=d[i-2]+2*sum; sum+=d[i]; } while(cin>>n,n!=-1) { cout<<d[n]<<endl; } return 0; }
原文：http://www.cnblogs.com/pach/p/6666383.html