题目链接：http://poj.org/problem?id=2229
思路：“动态规划”问题
只需要列三个连续数字N即可发现：1.N为奇数时，f(n)=f(n-1)
2.N为偶数时，f(n)=f(n-1)+f(n/2)
因为此时N-1为基数，N-1情况的每一行第一个数一定是1，所以加上一个1时，就相当于在前面直接加一个1或者与 “后面” 的1组成2。
ac代码：
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <string.h> #define MOD 1000000000 int N; int dp[1000005]; int main(void){ int num=1; scanf("%d",&N); dp[1]=1; for(int i=2;i<=N;i++){ if(i&1==1){ dp[i]=dp[i-1]; }else{ dp[i]=(dp[i-1]+dp[i>>1])%MOD; // 此处一定要取模 } } printf("%d\n",dp[N]); return 0; }
有一个小技巧：
按位操作
原文：https://www.cnblogs.com/jaszzz/p/12590888.html
