hdu 5366 简单递推

记f[i]为在长度是i的格子上面至少放一个木桩的方法数。考虑第i个格子，有放和不放两种情况。

1.如果第i个格子放了一个木桩，则i - 1和i - 2格子上面不能放木桩，方案数为：f[i - 3] + 1

2.如果第i个格子没有放木桩，则方案数为：f[i - 1]

然后递推即可。

#include <iostream>
using namespace std;

typedef long long ll;
const int N = 61;
ll f[N];

void init()
{
    f[1] = 1;
    f[2] = 2;
    f[3] = 3;
    for ( int i = 4; i < N; i++ )
    {
        f[i] = f[i - 1] + f[i - 3] + 1;
    }
}

int main ()
{
    init();
    int n;
    while ( cin >> n )
    {
        cout << f[n] << endl;
    }
    return 0;
}