509. Fibonacci Number

T: O(n)

S: O(n)

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

1 0

dp_i = dp_i_1 + dp_i_2

if get dp_i => do right shift value to

so

dp_i_2 = dp_i_1;

dp_i_1 = dp_i;

所以最後結果會在 dp_i_1 上, 因為最後 dp_i 給了 dp_i_1

T: O(n)

S: O(1)

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int dp_i_2 = 0;
        int dp_i_1 = 1;
        for (int i = 2; i <= n; i++) {
            int dp_i = dp_i_1 + dp_i_2;
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i_1;
    }
}

請畫圖

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int dpi2 = 0;
        int dpi1 = 1;
        for (int i = 2; i <= n; i++) {
            int dpi = dpi2 + dpi1;
            dpi2 = dpi1; // notice order, this put first
            dpi1 = dpi; // at last, this ans
        }
        return dpi1;
    }
}

// i-2. i-1 i 
//      i-2 i-1

// => i-2 = i-1
// =>.i-1 = i