主題
題目連結：
題目大意：
輸入有多筆測試資料，每筆佔一列。每列給定一正整數 n （1 ≦ n ≦ 76），代表有一種特殊的無向圖其有 n 個節點（如下圖所示）。
試問有多少方法可以從中取出一部份的節點成為一子集合使得：
沒有任何節點是相鄰的（相鄰節點為如上圖的節點 1 與節點 2 這種有邊相接之節點）；
加入其他未取的節點到此子集合中必會與其中某些節點相鄰。
例如 n = 5，合法的子集合為以下四種：
{ 1, 3, 5 } 、 { 1, 4 } 、 { 2, 4 } 、 { 2, 5 }
範例輸入：
1
2
3
4
5
30
範例輸出：
1
2
2
3
4
4410
解題思維：
考慮一個足夠大的 n 值（此例為 n ≧ 4），並假設 D[i] 為 i 個節點能取的所求子集合之方法數。
可以看到當我們取第 n 個節點時，第 n - 1 個節點不可能會被取；相反地，當取第 n - 1 個節點時，就取不了第 n 個節點。而且因為所求之子集合定義的緣故，我們必須取節點 n 與節點 n - 1 兩者其中之一。
因此，D[n] = (有取節點 n 的方法數) + (有取節點 n - 1 的方法數)。
而有取節點 n 的方法數恰為 D[n - 2]。為何？因為正如 n 個節點，有 n - 2 個節點時，你必須取節點 n - 2 或是節點 n - 3 。
不管如何，一定符合子集合的第一條性質——取的節點之間必不相鄰。
那麼第二條性質呢？假設你取的是節點 n - 2 （< n - 2 的節點隱含於 D[n - 2] 裡所以不需討論），而你唯一介於 n ～ n - 2 之間的節點只有節點 n - 1，而取它將會與節點 n 和節點 n - 2 相鄰；如果取的是節點 n - 3，則剩下 n - 1 與 n - 2，前者與節點 n 相鄰、後者與節點 n - 3 相鄰。所以實際上第二條性質也符合。
類似地，有取節點 n - 1 的方法數恰好為 D[n - 3] （將上面的論述的節點編號全部 - 1 即可得到）。
所以我們得到了一個遞迴式：
D[n] = D[n - 2] + D[n - 3]
而我們可以先建表（先求出較小 n 值，然後一路推到大的 n 值。已知 D[1] = 1 、 D[2] = 2 、 D[3] = 2）。然後對輸入的 n 值，輸出對應之 D[n]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
