记忆化搜索求斐波那契数列的土亢

发表于 更新于 分类于 阅读次数：

闲来无事刷个题目用所有方法解一遍斐波那契，没想到在记忆化翻车了

呆码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int fib(int n) {
        vector<int> memo(n + 1, -1);
        memo[0] = 0;
        memo[1] = 1;

        function<int(int)> mdfs = [&](int i) -> int {
            if(i <= 1) return i;

            if(memo[i] != -1) return memo[i];

            memo[i] = mdfs(i - 1) + mdfs(i - 2);

            return memo[i];
        };
        
        return mdfs(n);
    }

看到代码通不过案例真的破防，检查了很多遍发现lambda函数没有问题，其他地方都看起来很河狸。

也问了gpt-4o, 同样没有给我正确的解释，对于gpt来说还是超前了嘛(黑人问号)

最后解决问题是因为这段代码只有n = 0时无法通过，所以我加代码又重试了两次， 都通过了，第一次是在函数开头加了if (n <= 1) return n;第二次是将第4行的memo[1] = 1;改为if(n > 0) memo[1] = 1;

! 诶，立马意识到是memo数组出了问题, 所以将代码改了一个地方：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int fib(int n) {
        vector<int> memo(n + 10, -1);		// 改为了n + 10, n == 0时memo数组长度只有1, 那么第4行的memo[1] = 1数组越界
        memo[0] = 0;
        memo[1] = 1;

        function<int(int)> mdfs = [&](int i) -> int {
            if(i <= 1) return i;

            if(memo[i] != -1) return memo[i];

            memo[i] = mdfs(i - 1) + mdfs(i - 2);

            return memo[i];
        };
        
        return mdfs(n);
    }

至此， 精神状态又美丽了几分。