UVA 11069 - A Graph Problem

Problem link

Keyword: Fibonacci numbers, DP

Algorithm:

It's a DP problem.
If we select the first cell, then then second cell can never be selected again. That is, we'll have ans[ i-2 ] solutions for that situation.
If we don't select the first cell, we must select the second cell since if we don't select the second one, we have to select the first according to the rule given, and we must not  select the third cell because of that. In this situation, we have another ans[ i-3 ] ways.
So we can conclude that ans[ i ] = ans[ i-2 ] + ans[ i-3 ].

Code:

#include<cstdio>

int main()
{
    int ans[ 77 ] = { 1, 1, 2 }, n;
    for( int i = 3; i < 77; ++i )
        ans[ i ] = ans[ i-2 ] + ans[ i-3 ];

    while( scanf( "%d", &n ) != EOF )
        printf( "%d\n", ans[ n ] );

    return 0;
}