蓝桥杯备考：DFS之记忆化搜刮

如图，这道题的通例解法就不用我们多说了

1. class Solution {
2. public:
3.     int dfs(int n)
4.     {
5.         if(n==1 || n == 0) return n;
6.         return dfs(n-1) + dfs(n-2);
7.     }
8.     int fib(int n) {
9.         return dfs(n);
10.     }
11. };

复制代码

我们主要是为了引出我们的记忆化搜刮的剪枝策略，我们用一张图来分析一下

优化后的代码

1. class Solution {
2. public:
3.     int memo[35];
4.    
5.     int dfs(int n)
6.     {
7.         if(memo[n]!= -1) return memo[n];
8.         if(n==1 || n == 0) return n;
9.         memo[n] = dfs(n-1)+dfs(n-2);
10.         return memo[n];
11.     }
12.     int fib(int n) {
13.         memset(memo,-1,sizeof (memo));
14.         return dfs(n);
15.     }
16. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。