记忆化搜索
——即把搜过的地方记录下来,后面再搜的时候直接取就好了
题解:
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 }