http://www.cnblogs.com/skyiv/archive/2010/03/27/1698550.html

关键点在于通过记录一个数被分解的方案中包不包含1来考虑。

得出结论有:

f[2*N+1] = f[2*N]

f[2*N] = f[2*N-1] + f[N]

f[2*N] = f[0]+f[1]+...+f[N]

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MaxN = 100;int f[MaxN+5];int sum[MaxN+5];int N;void init() {    f[0] = 1, f[1] = 1, f[2] = 2;    sum[0] = 1, sum[1] = 2, sum[2] = 5;    for (int i = 3; i <= MaxN; i += 2) {        f[i] = f[i-1] = sum[i/2];        sum[i-1] = sum[i-2] + f[i-1];        sum[i] = sum[i-1] + f[i];    }}int main() {    init();    while (scanf("%d", &N) != EOF) {        printf("%d\n", f[N]);    }    return 0;}