POJ 2663 Tri Tiling dp 画图找规律

状态：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;

}

巴特西

POJ 2663 Tri Tiling dp 画图找规律

最新文章

热门文章