此代码用于以后方便复习使用，仅供参考。
数的计算 时间限制: 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;}新闻热点
疑难解答
