【动态规划】【记忆化搜索】CODEVS 1011 数的计算 2001年NOIP全国联赛普及组

设答案为f(n)，我们显然可以暴力地递归求解：

f(n)=f(1)+f(2)+……+f(n/2)。

但是n=1000，显然会超时。

考虑状态最多可能会有n种，经过大量的重复计算，所以可以记忆下来，减少不必要的计算。

 1 #include<cstdio>
 2 using namespace std;
 3 int n;
 4 long long memory[1001];
 5 long long f(int cur)
 6 {
 7     if(memory[cur]) return memory[cur];
 8     long long res=1;
 9     for(int i=1;i<=(cur>>1);i++) res+=f(i);
10     return memory[cur]=res;
11 }
12 int main()
13 {
14     scanf("%d",&n);
15     memory[1]=1;
16     printf("%lld
",f(n));
17     return 0;
18 }