本文共 2011 字，大约阅读时间需要 6 分钟。

题意：给定一个数N，要求出用2的次幂组成的等式的和等于N，输出有多少个符合条件的等式。如7，输出6：

1. 1+1+1+1+1+1+1
2. 1+1+1+1+1+2
3. 1+1+1+2+2
4. 1+1+1+4
5. 1+2+2+2
6. 1+2+4
   限制条件：1<=N<=1000000，结果对1e9取余。

这道题可以dp来做。

设置一个二维数组dp[i,j]，以及辅助数组c[i]，c[i]表示2ⁱ。 状态：dp[i,j]表示用2⁰,2¹,…,2^i-1,2ⁱ相加得到j时，最多有多少种情况： 状态转移方程： 1.当j<c[i]时，表示无法用2ⁱ加入等式使之和为j，故dp[i,j]=dp[i-1,j]； 2.当j>=c[i]时，此时可以用2ⁱ，2ⁱ可以用0个或者若干个： A.使用0个时，此时有dp[i-1,j]种方法； B.使用若干个时，此时有d[i,j-c[i]]种方法（注意！是dp[i,j-c[i]]而不是dp[i-1,j-c[i]]，这与完全背包问题的道理一样） 因此，当j>=c[i]时，dp[i,j]=dp[i-1,j]+dp[i,j-c[i]]，注意这里不是取其中最大的，而是相加，好好理解一下。 故有： dp[i,j]=:

j<c[i]：dp[i-1,j]

j>=c[i]：dp[i-1,j]+dp[i,j-c[i]] 数据初始化：

1.dp[0,1~N]=1;

2.dp[0~N,0]=1. 第二种情况会比较匪夷所思，按理来说，当j为0时，应当没有符合条件的等式成立，因此dp[0~N,0]应赋值0，但是确实只能这样，试想dp[1,2]=dp[0,2]+dp[1,2-2]=dp[0,2]+dp[1,0],如果dp[1,0]赋值为0，那么dp[1,2]=1，但实际答案为2，因此这种初始化是不可取的，只能将dp[0,…,N,0]赋为1。你可以这样想，dp[0-N,0]存储的是j单独用2ⁱ组成的等式，而这种等式显然只有一个，因此应等于1。

然而，很遗憾的是，这道题用二维数组做的话，N的值取很大时会超时，因此，只能将dp[i,j]降维成dp[j]，即使用滚动数组来完成，这样会节省一些时间（看下面的代码就知道），虽然不会多很多，但就是恰好，有些数组卡到了用二维数组的时间，用一维的就恰好过了。

AC代码（用滚动数组）

#include 
   
    #include 
    
     #include 
     
      using namespace std;int dp[1000005],c[25];int n,i,j;int main(){    scanf("%d",&n);    c[0]=dp[0]=1;    for(i=1;i<=20;i++)    c[i]=c[i-1]<<1;   //巧妙的利用了位运算处理2的次幂    for(i=0;i<=20&&c[i]<=n;i++)        for(j=c[i];j<=n;j++)      //起点是c[i]，而非0，这就是为什么用滚动数组会稍微快的原因            dp[j]=(dp[j-c[i]]+dp[j])%1000000000;    cout<
      
       <
      
     
    
   

这个AC的代码是copy网上的大佬的，原博客网址为：

下面是二维数组的代码：

#include
   
    #include
    
     using namespace std;long long dp[20][1000001];long long c[20]={1};int main(){//while(1){	int n,i,j,k=0;	scanf("%d",&n);	//while((int)pow(2,k)<=n)	  //  k++; 	for(i=1;i<=n;i++)	{		dp[0][i]=1;	}dp[0][0]=1;	for(i=0;i<=19;i++)	    dp[i][0]=1;//	for(i=0;i<=k-1;i++)//	    c[i]=(int)pow(2,i);     for(i=1;i<=19;i++)        c[i]=c[i-1]<<1;   	for(i=1;i<=19&&c[i]<=n;i++)	{		for(j=c[i];j<=n;j++)		{			if(j
    
   

事实上，这道题还可以用规律来做：

当数字大于2时，当为奇数则a[n]=a[n-1];

当为偶数是 a[n]=a[n-1]+a[n/2]；

同样是参照上面的博客的。

小结：

1.此题要多参考大佬的代码，关于状态方程的推导，滚动数组的运用，以及巧妙的利用位运算处理数据； 2.如果在平时遇到这种题，还是考虑找规律来解答吧，因为数据太大了，用dp很容易就超时。

转载地址：http://sfdci.baihongyu.com/