题目

一个正整数可以表示为多个正整数相加的表达式，表达式中的各个正整数要求都是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

分析

方法一

使用的是数学的方法。

这种方法太巧妙了！！

1. 首先，一个memo[n]都初始化为为1，表示n拆分为n个1相加，这种情况。（2^0 =1）
2. 在循环中以此计算通过将1+1合并为2,2+2合并为4，使用这种方法构造出来的新的拆分方法
   k就是要合并成为的数。
   同时只有大于k=2^m次方的数，才能通过这种方法拆分，所以在for中，j的起始为j=k。
3. 最精妙的是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;
}