https://www.luogu.com.cn/problem/P1028
这道题刚开始的做法是暴力递归，但是时间复杂度太高了过不去，所以就看了一下递归的优化，递归可以用递推和记忆化搜索来进行优化，递归是从上往下，到达出口之后再回溯，其中不乏有许多重复计算，一旦数据量大一些，时间复杂度就会很高。递推是从下往上，所以相对于递归不会有重复计算，也省去了回溯这一操作；记忆化搜索是记录下递归操作中已经算出来的结果，等下一次用到的时候可以直接调用，相当于也是省去了重复计算。
这道题是计算从数的左边加一个小于等于它一半的数?，直到不能再加为止（也就是递归出口为1），?具体的数不用记录，故在每次调用的基础上加一就可以（注意这里的和不能设为全局变量，会把之前的结果也加进来）。发现自己对递归，递推还有搜索这些算法学习的都不是很好，明天开始先刷这几个吧。如果有不对或者改进的地方，希望大佬们予以指正。还有还有大家有关于算法刷题的一些小建议或者经验之类的吗？本蒟蒻刚开始刷算法不久，还有一点小迷茫，尤其对上面三个递归，递推，还有搜索之类的。
#include <bits/stdc++.h>
using namespace std;
int f[10000];
int shu(int n){ //记忆化搜索，用数组来保存已经算过的值，避免重复计算
if(n == 1)
f[1] = 1;
int ans = 1;
if(f[n] != 0) return f[n]; //避免重复计算
for( int i = n/2; i > 0; i --){
ans += shu(i);
f[n] = ans; //第一次把f[n]想成了f[i],如果是f[i]的话，每次调用的结果更新的都是f[1]，但是实际上循环完之后ans的结果是函数参数n的结果
}
return ans;
}
int main(){
int n;
cin >> n;;
cout << shu(n);
return 0;
}