1 #include <iostream> 2 3 using namespace std; 4 5 int dp[1000001]; 6 7 int main() { 8 int n; 9 while (cin >> n) { 10 dp[1] = 1; 11 dp[2] = 2; 12 for (int i = 3; i <= n; ++i) { 13 if (i % 2 == 1) 14 dp[i] = dp[i - 1]; 15 else 16 dp[i] = dp[i - 1] + dp[i / 2]; 17 dp[i] %= 1000000000; 18 } 19 cout << dp[n] << endl; 20 } 21
摘抄：i 为 奇数时，拆分跟前面的i-1是一样的，自己写几组就知道了，不用多说。关键是 i 为偶数时：当拆分中不含1时，则拆分情况最小分到2，则拆分情况跟i/2是一一对应的；当拆分中含有1时，先把这个1拿出来，剩下的i-1进行拆分，情况跟i-1的拆分时一一对应的；而这两种拆分情况是互不相交的（因为一种没1，一种有1），则加起来就是 i 为偶数时的拆分情况。
好方法，自己就想不到 呜呜
原文：http://www.cnblogs.com/dreamer123/p/5173833.html