optimization - 动态规划记忆的时间复杂度

Question

在寻找第 n 个斐波那契数的动态编程/记忆解决方案中，我无法理解为什么使用递归的自上而下的方法也是 O(n)。

我理解为什么迭代自下而上的解决方案是 O(n)，因为由于下面显示的 for 循环，我可以清楚地看到这一点。

public static int fib(int n){
    if(n<3)return 1;
    int memo[] = new int[n+1];
    memo[1]=1;memo[2]=1;
    for (int i = 3; i <=n ; i++) {
        memo[i]=memo[i-1]+memo[i-2];
    }
    return memo[n];
}

但是，当涉及到自上而下的方法时：

public static int fib(int n,int memo[]) {
    if (memo[n] != 0) return memo[n];
    if (n < 3) return 1;
    memo[n - 1] = fib(n - 1, memo);
    memo[n - 2] = fib(n - 2, memo);
    return memo[n - 1] + memo[n - 2];

}

我很难理解为什么这也是 O(n)，我读过这是因为有 n 个状态/子问题并且每个状态都需要 O(1)，但我真的不明白为什么这是有道理的。

我也尝试阅读这个类似问题的答案，但我也不明白答案。

标签： optimizationdynamic-programmingfibonaccimemoization