题目
一个正整数可以表示为多个正整数相加的表达式，表达式中的各个正整数要求都是2的幂。例如给定正整数7，它有下列六个符合要求的表达式：
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
因此，正整数7符合条件的表达式个数是6.
编写一个程序，对于给定的正整数N(1 <= N <= 1,000)，输出符合条件的表达式个数。
要求：时间复杂度不高于O(N)。
输入描述:一个整数（>=1并且<=1000）
输出描述:表达式个数
示例1：
输入7
输出6
分析
方法一
使用的是数学的方法。
这种方法太巧妙了！！
- 首先，一个
memo[n]都初始化为为1，表示n拆分为n个1相加，这种情况。（2^0 =1） - 在循环中以此计算通过将
1+1合并为2,2+2合并为4，使用这种方法构造出来的新的拆分方法
k就是要合并成为的数。
同时只有大于k=2^m次方的数，才能通过这种方法拆分，所以在for中，j的起始为j=k。 - 最精妙的是
dp[j]=dp[j]+dp[k]
这一句，完美的包含了，所有可能的组合。
同时考虑了，不能合并部分还可以由小于k的数相加的来。
比如：
以7为例，初始dp[7]=1，k=2时dp[7]=dp[7]+dp[5]。其中dp[5]=dp[5]+dp[3]的来，而dp[3]=dp[3]+dp[1]的来。
这个dp[1]的意思是，1这个数，如果使用，小于k=2的数来相加得到的所有拆分法，（也就是1=1）。
最终dp[7]=4
当k=4时，dp[7]=dp[7]+dp[3]，dp[3],表示，7-4=3，剩下的3，如果使用1,2来拆分的话，有2种情况。然后dp[7]=4+2=6。dp[7]表示，7由1,2拆分出来可能性。
在例如,17, k=8,dp[23]=dp[23]+dp[15],dp[15]=dp[15]+dp[7],这里的dp[7]就等于，7由1,2,4拆分的可能结果
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int dp[n+1];
//初始化为1,表示n拆分为n个1,这一种拆分方法
for(int i=0;i<=n;i++)
{
dp[i]=1;
}
int k=2;
while(k<=n)
{
//第一次循环表示，通过将两个1，合并为2，得到的新的方法。
//因为只有大于2的数才能够使用该拆分方法，所以j初始为2
//以后拆分方法为4，8，16
for(int j = k;j<=n;j++)
{
//原有的方法个数，加上新的拆分方法个数
//最精妙
dp[j]+=dp[j-k];
}
k*=2;
}
cout<<dp[n]<<endl;
}
方法二
使用深度优先搜索的变形。
在遍历过程中要保证不能重复，这里使用：总是先分解出大数，从达到小的顺序排列来保证。
例如11=4+4+2+1。而后续的遍历过程中不会出现11=4+2+4+1
void fenjie2_ass(int remain,int k,int &result)
{
if(remain < 0)
{
return;
}
if(remain == 0)
{
result++;
return;
}
while(remain < (1<<k))
{
k--;
}
for(int i = k;remain>=(1<<i);i--)
{
int tmp = remain - (1<<i);
fenjie2_ass(tmp,i,result);
}
}
int fenjie2(int n)
{
int remain=n;
int k=0;
while(remain)
{
k++;
remain/=2;
}
remain = n;
int result = 0;
fenjie2_ass(remain,k,result);
return result;
}
