http://poj.org/problem?id=2229
先把题目连接发上。题目的意思就是：
把n拆分为2的幂相加的形式，问有多少种拆分方法。
看了大佬的完全背包代码很久都没懂，就照着网上的写了动态规划的思路
先把组合数存进数组
任何dp一定要注意各个状态来源不能有重复情况。
根据奇偶分两种情况
如果n是奇数则与n-1的情况相同，它只比前一个偶数多了一个1，并不能合成一个2的幂，所以是一样的。
如果n是偶数则还可以分为两种情况，有1和没有1。这样分可以保证两种情况没有重复）
举个栗子 8 有1 11111111 1111112 等等
没1 2222 224 等等
这么算是为了防止重复运算=。=，虽然我也不是很清楚为什么......
对于有1的情况可以直接拆出两个1（拆一个也行，但变成奇数之后一定会拆另一个），然后变为n-2的情况。(就是说，dp[i]=dp[i-1]或者dp[i]=dp[i-2]都是可以的，因为当dp为i-1时,i-1是奇数，根据第一条,dp[i-1]==dp[i-2])
对于没有1的情况可以直接将其转化为n/2。因为n拆分出所有的数字都是2的倍数。只需要将每种拆分结果中的数字都除以2就会与n/2的一种拆分相对应。由递推可以求得
先把前十位的答案写出来
1
1
2
2
3
2
4
4
5
4
6
6
7
6
8
10
9
10
当我们取8时 考虑不带1的话 2222 224 44 8 四种，和dp[4]的结果是一样的
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; long long dp[1000005]={0}; int main() { int n,i; memset(dp,0,sizeof(dp)); dp[1]=1;dp[2]=2; for(i=3;i<=1000000;i++) { if(i%2==1)//奇数 dp[i]=dp[i-1]; else//偶数 dp[i]=dp[i-2]+dp[i/2];//要把两种情况加起来 if(dp[i]>1000000000) dp[i]-=1000000000; } //上面在用数组存下每一种情况 while(cin>>n) cout<<dp[n]<<endl; return 0; }