題目描述

我們要求找出具有下列性質數的個數(包含輸入的自然數n):
先輸入一個自然數n(n≤1000),然后對此自然數按照如下方法進行處理:
1.不作任何處理;
2.在它的左邊加上一個自然數,但該自然數不能超過原數的一半;
3.加上數后,繼續按此規則進行處理,直到不能再加自然數為止.

輸入格式

1個自然數n(n≤1000)

輸出格式

11個整數，表示具有該性質數的個數。

輸入輸出樣例

輸入

6

輸出

6
(說明/提示:滿足條件的數為:6，16，26，126，36，136)　
 
 

我的分析

?初看此題，頓覺簡單：不就是遞歸嘛，窮舉所有情況不就完了嗎，豈能難得住我？(￣▽￣)

?說時遲那是快，我三下五除二地便寫出如下解法：

#include<iostream>
using namespace std;
int func(int n){
    int count=0;
    for(int i=1;i<=n/2;++i){//枚舉該數左邊可能的相鄰數
     count += 1+fun(i);//仍是兩種情況：左邊無數/左邊有數
    }
    return count;
}
int main(){
    int n;
    cin>>n;
    int count=0;
    count=1+func(n); //兩種情況：左邊無數/左邊有數
    cout<<count<<endl;
    return 0;
}

?然后我信心滿滿地等待著AC結果，然而卻顯示——


?◢▆▅▄▃ 崩╰(〒皿〒)╯潰 ▃▄▅▆◣大部分case都沒有過，我感覺收到了此題極大的羞辱！
?于是，我不得不思考更高效的解法。如上所示，之前采取的遞歸的思路是自上而下：我們從原數開始逐步向左推進，分析該數左邊可能出現的的所有數字排列。我靈機一動，不妨換一個思路，自下而上，從 1 分析起走，如數字 1 只有 1 種情況，就是 1 本身；數字 2 有 2 種情況: 2,12 ;數字 3 有 2 種情況: 3,13 ;數字 4 有 4 種情況: 4,24,14,124 …我們不難發現，前面的情況其實可以劃歸為后面出現的情況的子問題，如 12=1+2,124=12+4 等等，這也就是動態規劃的基本思想：將復雜問題劃歸為簡單的子問題，最終由基準情形逐步推導出所有情形。如果我們用 dp[i] 表示由數字 i 推導出的的所有滿足性質的數的數量，那么有如下遞推關系式：

?dp[1]=1
?dp[2]=1+dp[1]=2
?dp[3]=1+dp[1]=2
?dp[4]=1+dp[2]+dp[1]=4
?dp[5]=1+dp[2]+dp[1]=4
?dp[6]=1+dp[3]+dp[2]+dp[1]=6
?…
?dp[i]=1+dp[1,2,3,…,j] (j=i/2)

?找準了基準情形： i=1 ，列出了遞推式:dp[i]=1+dp[1,2,3,…,j] (j=i/2),那么動態規劃的題目就迎刃而解啦。（ノ≧?≦）ノ
該題的最終代碼非常簡潔，只有以下幾行：

#include<iostream>
using namespace std;
int main(){
    int n; //原數
    cin>>n;
    int dp[n+1]; //dp數組記錄每種子問題的情況數
    for(int i=1;i<=n;i++){//迭代以１－ｎ結尾的每一個子問題
        dp[i]=1;  //只有該數自己本身算１種情形
        for(int j=i/2;j>=1;j--){
            dp[i] += dp[j];　//加上子問題的情形數
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

?現在所有情況都能AC啦！


以后暴力求解時一定要三思而后行了…