爬天梯 + 放苹果 （记忆化搜索大大优化时间复杂度）

记忆化搜索

——即把搜过的地方记录下来，后面再搜的时候直接取就好了

 题解：

 1 #include <iostream>
 2 using namespace std;
 3 #define ll long long
 4 const int N = 100;
 5 ll a[N], n;
 6 ll dfs(ll n)
 7 {
 8     if (n <= 1)
 9         return 1;
10 
11     if (!a[n])
12         a[n] = dfs(n - 1) + dfs(n - 2);
13     // 记忆化搜索的核心（这样能减少好多重复代码，防止无用的递归浪费时间）
14 
15     return a[n];
16 }
17 
18 int main()
19 {
20     cin >> n;
21     cout << dfs(n);
22     return 0;
23 }

 题解1：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int m, n;
 4 
 5 int dp(int m, int n)
 6 {
 7     if (n <= 0 && m == 0)
 8         return 1; // 注意退出条件的判断 ！！！！！！！！！
 9     if (n <= 0 && m != 0)
10         return 0;
11     if (n > m) // 盘子数大于苹果数，则至少有n - m个空盘子
12         return dp(m, m);
13     else
14         // 否则，则分为两种情况——有空盘子（有空盘子则从1个空盘开始枚举）
15         // 和没有空盘子 （没有空盘即每个盘子先放一个苹果）
16         return dp(m, n - 1) + dp(m - n, n);
17 }
18 
19 int main()
20 {
21     int t;
22     cin >> t;
23     while (t--)
24     {
25         cin >> m >> n;
26         cout << dp(m, n) << endl;
27     }
28 
29     return 0;
30 }

题解2（记忆化搜索）：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 40;
 4 int m, n;
 5 int a[N][N];
 6 
 7 int dp(int m, int n)
 8 {
 9     if (n <= 0 && m == 0)
10         return 1; // 注意退出条件的判断 ！！！！！！！！！
11     if (n <= 0 && m != 0)
12         return 0;
13     if (n > m)
14     { // 盘子数大于苹果数，则至少有n - m个空盘子
15         if (!a[m][m])
16             a[m][m] = dp(m, m);
17         return a[m][m];
18     }
19     else
20     {
21         // 否则，则分为两种情况——有空盘子（有空盘子则从1个空盘开始枚举）
22         // 和没有空盘子 （没有空盘即每个盘子先放一个苹果）
23         if (!a[m][n])
24             a[m][n] = dp(m, n - 1) + dp(m - n, n);
25         return a[m][n];
26     }
27 }
28 
29 int main()
30 {
31     int t;
32     cin >> t;
33     while (t--)
34     {
35         cin >> m >> n;
36         cout << dp(m, n) << endl;
37     }
38 
39     return 0;
40 }