整数划分变形，由2^k组成。
整数划分中一个节约内存的技巧，平时我们使用dp[i][j]维护用不大于j的数组合成i的方案数，所以必须dp[i-j][j]->dp[i][j]。这样就需要二位，如果用一维dp[i-j]->dp[i]就会导致重复选取的情况。其原因在于dp[i-j]在计算的过程已经把大于j的组合求完了，就会重复。那么很自然地想到把j地遍历放在外面，这样每次求解的时候，dp[i-j]必然只求解了小于等于j的情况。
#include <iostream> #include <algorithm> #include <vector> #include <cstring> #define LL int const LL mod=1000000000; const LL N=1000006; LL dp[N]; LL bit[22]; using namespace std; int main() { cin.sync_with_stdio(false); LL n; int t; bit[0]=1; for(int i=1;i<22;i++)bit[i]=bit[i-1]*2; dp[0]=1; for(int i=0;bit[i]<N;i++) { for(int j=bit[i];j<N;j++) dp[j]+=dp[j-bit[i]],dp[j]%=mod; } while(cin>>n) { cout<<dp[n]<<endl; } }
原文：http://www.cnblogs.com/LukeStepByStep/p/7742221.html