蓝桥杯备考：DFS之记忆化搜索
如图，这道题的常规解法就不用我们多说了
class Solution {
public:
int dfs(int n)
{
if(n==1 || n == 0) return n;
return dfs(n-1) + dfs(n-2);
}
int fib(int n) {
return dfs(n);
}
};我们主要是为了引出我们的记忆化搜索的剪枝策略，我们用一张图来说明一下
优化后的代码
class Solution {
public:
int memo[35];
int dfs(int n)
{
if(memo[n]!= -1) return memo[n];
if(n==1 || n == 0) return n;
memo[n] = dfs(n-1)+dfs(n-2);
return memo[n];
}
int fib(int n) {
memset(memo,-1,sizeof (memo));
return dfs(n);
}
};