此代碼用于以后方便復習使用，僅供參考。

數的計算 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver

題解 查看運行結果 題目描述 Description 我們要求找出具有下列性質數的個數(包含輸入的自然數n):

先輸入一個自然數n(n<=1000),然后對此自然數按照如下方法進行處理:

不作任何處理;

在它的左邊加上一個自然數,但該自然數不能超過原數的一半;

加上數后,繼續按此規則進行處理,直到不能再加自然數為止.

輸入描述 Input Description 一個數n

輸出描述 Output Description 滿足條件的數的個數

樣例輸入 Sample Input 6

樣例輸出 Sample Output 6

數據范圍及提示 Data Size & Hint 6個數分別是：

6

16

26

126

36

136

思路： 我的思路是，記憶化dfs。根據之前算出的結果，去掉重復計算，直接返回結果。不知道有沒有更好的方法，歡迎分享?。?/p>#include<iostream>#include<string.h>#include<math.h>using namespace std;int dp[1001];int dfs(int n){ if(dp[n]!=-1)return dp[n];//記憶化搜索，如果有直接返回數值 if(n==1){return dp[1]=1;}//dfs邊界問題，到界直接返回 else { int sum = 1;//算上自身個數，所以從1開始累加 ，如2，加上自身2，和下面返回的結果1，一共2種可能 for(int i = 1;i<=n/2;i++){ sum+=dfs(i);//這里的dfs返回的是前面能添加數的種類數 } return dp[n] = sum;//將此時n統計的結果進行返回，返回到對應角標數組中保存 }}int main(){ int n; cin>>n; memset(dp,-1,sizeof(dp)); cout<<dfs(n)<<endl; return 0;}