11069:A Graph Problem

問題文
http://uva.onlinejudge.org/external/110/11069.html

1~nまでの頂点が一直線につながっている。このグラフから、どの頂点も隣り合っていない物の中で、これ以上頂点を追加できないものの数を数えよ。

dp[頂点]:=場合の数
とすると、頂点が2つ前のものと、3つ前のものの和がその頂点の場合の数となる。

#include <iostream>
#include <cstring>
using namespace std;
 
int dp[80],n;
int main(){
  memset(dp,0,sizeof(dp));
  dp[0]=1;
  dp[1]=1;
  dp[2]=2;
   
  for(int i=3;i<77;i++){
    dp[i]=dp[i-2]+dp[i-3];
  }
 
  while(cin >> n){
    cout << dp[n] << endl;
  }
 
  return 0;
}