CN10-Fibonacci

tags

Dynamic Programming, Fast Modular Exponentiation

source

leetcode-cn

Edge Cases

Solution 1 - Dynamic Programming

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        int constant = 1000000007;
        int minusOne = 1, minusTwo = 0, fib = 0;
        for (int i = 2; i <= n; i++) {
            fib = (minusOne + minusTwo) % constant;  // must
            minusTwo = minusOne;
            minusOne = fib;
        }

        return fib;
    }
}

Complexity

• time: O(n)
• space: O(1)

Solution 2 - Matrix

Think Fibonacci sequence as following form:

[1 1]^n = [F(n+1) F(n))]
[1 0]     [F(n)   F(n-1)]

To get F(n), compute the nth matrix. It’s important to use FME, or the time complexity will be the same as Solution 1.

Complexity

• time: O(lgN)
• space: O(1)

Solution 3 - Faster Matrix

The Solution 2 contains some redundant computations. We just need F(n+1) and F(n). Follow this idea, we can get two equations for just computing necessaries elements in the matrix. See “Fast Doubling” in DEVONThink.

Another way with same idea is from SICP-Exercise 1.19:

1. Consider transformation T(p, q), which transforms pair (a, b) according to a <- bq+aq+ap, b <- bp+aq. It can be represented as a matrix: [q+p, q] [q, p] (a, b) start from (1, 0) and (p, q) start from (0, 1)

2. To apply FME, we need to find p' and q' , so apply we apply T(p',q') to (a, b), we get the same effect of applying T(p, q) twice

3. Below equations can be easily obintained:

      q' = q^2 + 2pq
      p' = q^2 + p^2
   

Code:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (* 2 p q) (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Complexity

• time: O(lgN)
• space: O(1)