
# Fibonacci Number

## Description

[doc](https://leetcode.com/problems/fibonacci-number/)

## Solutions

### First Idea

```javascript
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n < 2) {
    return n
  }

  let pprev = 0
  let prev = 1
  let cur

  for (let i = 2; i <= n; i++) {
    cur = pprev + prev
    pprev = prev
    prev = cur
  }

  return cur
}
```

- Time Complexity: O(n)
- Space Complexity: O(1)

### Refined for Time

```javascript
const cached = []
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n < 2) {
    return n
  }

  let pprev = 0
  let prev = 1

  for (let i = 2; i <= n; i++) {
    cached[i] = pprev + prev
    pprev = prev
    prev = cached[i]
  }

  return cached[n]
}
```

- Time Complexity: O(n)
- Space Complexity: O(n)
