POJ.2229 Sumsets

1.Problem
http://poj.org/problem?id=2229

2.Idea
dp[i]: the answer when input is i.
We can see the following relation.
dp[i] = dp[i-1] if i is odd (sequence always includes '1', so we can exclude it)
dp[i] = dp[i-1] + dp[i/2] if i is even (first part is include '1' + second part is not include '1')


3.Source

 int n;  
 int dp[1000006];  
 int main()  
 {  
      cin >> n;  
      dp[1] = 1;  
      dp[2] = 2;  
      dp[3] = 2;  
      for (int i = 4; i <= n; i++) {  
           if (i % 2) dp[i] = dp[i - 1] % 1000000000;  
           else dp[i] = (dp[i - 1] + dp[i / 2]) % 1000000000;  
      }  
      cout << dp[n] << endl;  
      return 0;  
 }