洛谷P1028数的计算

https://www.luogu.org/problemnew/show/P1028

只用递归会超时，需要用递归型动规，用一个数组保存已经算过的值，避免重复计算。

求数字为n的方案数的最优子结构为：求数字从1到n/2的方案数之和再加上这个数字本身，即fn=f1+f2+...+f(n/2)+1，

边界为：1的符合条件的方案数只有它自己,即f1=1.

例：

f(6)=f(1)+f(2)+f(3)+1=1+2+2+1=6.

f1=1,f2=f1+1=1+1=2,f3=f1+1=1+1=2。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 //int cnt = 1;
 5 int dp[1010];
 6 int f(int n)//数字为n的方案数
 7 {
 8     if (n == 1)//1满足条件的只有它自己
 9     {
10         dp[n] = 1;
11         return dp[n];
12     }
13     if (dp[n] != 0)
14     {
15         return dp[n];
16     }
17     int e = n / 2;
18     int sum = 0;
19     for (int i = 1; i <= e; ++i)
20     {
21         sum += f(i);
22     }
23     dp[n] = sum + 1;//不为1的方案数除了从1到n/2的方案数之和还得加上这个数字自己
24     return dp[n];
25 }
26 int main()
27 {
28     int n;
29     memset(dp, 0, sizeof(dp));
30     cin >> n;
31     
32     cout << f(n)<< endl;
33     return 0;
34 }