題目

一個(gè)正整數(shù)可以表示為多個(gè)正整數(shù)相加的表達(dá)式，表達(dá)式中的各個(gè)正整數(shù)要求都是2的冪。例如給定正整數(shù)7，它有下列六個(gè)符合要求的表達(dá)式：
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
因此，正整數(shù)7符合條件的表達(dá)式個(gè)數(shù)是6.
編寫一個(gè)程序，對(duì)于給定的正整數(shù)N(1 <= N <= 1,000)，輸出符合條件的表達(dá)式個(gè)數(shù)。
要求：時(shí)間復(fù)雜度不高于O(N)。
輸入描述:一個(gè)整數(shù)（>=1并且<=1000）
輸出描述:表達(dá)式個(gè)數(shù)
示例1：
輸入7
輸出6

分析

方法一

使用的是數(shù)學(xué)的方法。

這種方法太巧妙了！！

1. 首先，一個(gè)memo[n]都初始化為為1，表示n拆分為n個(gè)1相加，這種情況。（2^0 =1）
2. 在循環(huán)中以此計(jì)算通過(guò)將1+1合并為2,2+2合并為4，使用這種方法構(gòu)造出來(lái)的新的拆分方法
   k就是要合并成為的數(shù)。
   同時(shí)只有大于k=2^m次方的數(shù)，才能通過(guò)這種方法拆分，所以在for中，j的起始為j=k。
3. 最精妙的是dp[j]=dp[j]+dp[k]
   這一句，完美的包含了，所有可能的組合。
   同時(shí)考慮了，不能合并部分還可以由小于k的數(shù)相加的來(lái)。
   比如：
   以7為例，初始dp[7]=1，k=2時(shí)dp[7]=dp[7]+dp[5]。其中dp[5]=dp[5]+dp[3]的來(lái)，而dp[3]=dp[3]+dp[1]的來(lái)。
   這個(gè)dp[1]的意思是，1這個(gè)數(shù)，如果使用，小于k=2的數(shù)來(lái)相加得到的所有拆分法，（也就是1=1）。
   最終dp[7]=4
   當(dāng)k=4時(shí)，dp[7]=dp[7]+dp[3]，dp[3],表示，7-4=3，剩下的3，如果使用1,2來(lái)拆分的話，有2種情況。然后dp[7]=4+2=6。dp[7]表示，7由1,2拆分出來(lái)可能性。

在例如,17, k=8,dp[23]=dp[23]+dp[15],dp[15]=dp[15]+dp[7],這里的dp[7]就等于，7由1,2,4拆分的可能結(jié)果

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int dp[n+1];

    //初始化為1,表示n拆分為n個(gè)1,這一種拆分方法
    for(int i=0;i<=n;i++)
    {
        dp[i]=1;
    }

    int k=2;
    while(k<=n)
    {
        //第一次循環(huán)表示，通過(guò)將兩個(gè)1，合并為2，得到的新的方法。
        //因?yàn)橹挥写笥?的數(shù)才能夠使用該拆分方法，所以j初始為2
        //以后拆分方法為4，8，16
        for(int j = k;j<=n;j++)
        {
            //原有的方法個(gè)數(shù)，加上新的拆分方法個(gè)數(shù)
            //最精妙
            dp[j]+=dp[j-k];
        }

        k*=2;
    }
    cout<<dp[n]<<endl;
}

方法二

使用深度優(yōu)先搜索的變形。
在遍歷過(guò)程中要保證不能重復(fù)，這里使用：總是先分解出大數(shù)，從達(dá)到小的順序排列來(lái)保證。
例如11=4+4+2+1。而后續(xù)的遍歷過(guò)程中不會(huì)出現(xiàn)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;
}