ACM 11069 A Graph Problem

用Dynamic Programming

第一個關鍵的觀察是：任何一個subset的最後一個元素必定為n或n-1
以n = 5為例，無論是哪個subset，結尾必定為4或5

第二個關鍵就是遞迴式：f(n) = f(n-2) + f(n-3)
同樣以n=5為例，我們已經知道結尾必定為4或5，因此所有subsets可以分成兩類：以4結尾和以5結尾

(1)以4結尾： 因為不能元素都不能相鄰，所以剩下的元素指可以是1、2。你會發現以4結尾的subsets數目其實就是f(2)
(2)以5結尾： 因為不能元素都不能相鄰，所以剩下的元素指可以是1、2、3。你會發現以5結尾的subsets數目其實就是f(3)
由(1) (2)可得知f(5) = f(3) + f(2)


#include <stdio.h>

int main(void)
{
    int i, table[76];
   
    table[0] = 1, table[1] = 2, table[2] = 2;
    for (i = 3; i < 76; i++)
        table[i] = table[i-2] + table[i-3];

    while (scanf("%d", &i) == 1)
        printf("%d\n", table[i-1]);

    return 0;
}