讨论/《零起步学算法》 - 例题讲解:斐波那契数/
《零起步学算法》 - 例题讲解:斐波那契数
共 2 个回复

我觉得记忆化递归的代码应该像这样写吧:

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fib(n, memo);
    }

    public int fib(int n, int[] memo) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (memo[n] == -1) {
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        }
        return memo[n];
    }
}
5

大佬,递归方法的空间复杂度是O(n),不是O(lgn)吧,是不是写错了