此代碼用于以后方便復習使用，僅供參考。
數的計算 時間限制: 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。根據之前算出的結果，去掉重復計算，直接返回結果。不知道有沒有更好的方法，歡迎分享??！
#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;}新聞熱點
疑難解答
