整数拆分问题：给定一个正整数n，将n拆分为若干数字的和，问有多少种方法？
此题为整数拆分问题的子问题，拆分出的数字要求是2的幂次。
定义dp[i][k]表示枚举到第k个数字时数字i的拆分方案数。
则有状态转移方程：
dp[i][k] = dp[i][k - 1] + dp[i - num[k]][k];
熟悉完全背包的朋友可以看出，这个方程和完全背包的状态转移方程如出一辙，第二维可以省去，只要将i从小到大枚举即可。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int MOD = 1000000000; 7 const int N = 1000001; 8 int dp[N]; 9 10 void init() 11 { 12 dp[0] = 1; 13 for ( int j = 0; ( 1 << j ) < N; j++ ) 14 { 15 for ( int i = ( 1 << j ); i < N; i++ ) 16 { 17 dp[i] += dp[i - ( 1 << j )]; 18 if ( dp[i] >= MOD ) dp[i] -= MOD; 19 } 20 } 21 } 22 23 int main () 24 { 25 init(); 26 int n; 27 while ( scanf("%d", &n) != EOF ) 28 { 29 printf("%d\n", dp[n]); 30 } 31 return 0; 32 }
此外还有递推的做法：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int MOD = 1000000000; 7 const int N = 1000001; 8 int dp[N]; 9 10 void init() 11 { 12 dp[1] = 1; 13 dp[2] = 2; 14 for ( int i = 3; i < N; i++ ) 15 { 16 if ( i & 1 ) 17 { 18 dp[i] = dp[i - 1]; 19 } 20 else 21 { 22 dp[i] = dp[i - 1] + dp[i >> 1]; 23 if ( dp[i] >= MOD ) dp[i] -= MOD; 24 } 25 } 26 } 27 28 int main () 29 { 30 init(); 31 int n; 32 while ( scanf("%d", &n) != EOF ) 33 { 34 printf("%d\n", dp[n]); 35 } 36 return 0; 37 }
原文：http://www.cnblogs.com/huoxiayu/p/4730971.html