# 509. Fibonacci Number



T: O(n)

S: O(n)

```java
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];
    }
}
```





&#x20;              1              0

dp\__i = dp\_i\_1 + dp\_i\_2_

if get dp\_i => do right shift value to&#x20;

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)_

```java
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;
    }
}
```



請畫圖

```java
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
```
