LeetCode Note Java 00509：Fibonacci Number

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 166 所需閱讀時間 ≈ 1 分鐘

經典題：費式數列。

題目

Fibonacci Number Easy

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

1
2
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

我的解法

經典題，就遞迴法或 Dynamic Programming 實作。

Dynamic Programming
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int n) {
        if (n < 2) {
          return n;
        }
        int[] fa = new int[n + 1];
        fa[0] = 0;
        fa[1] = 1;
        for (int i = 2; i < n + 1; i++) {
          fa[i] = fa[i - 1] + fa[i - 2];
        }
        return fa[n];
    }
}
遞迴法
1
2
3
4
5
6
7
8
class Solution {
    public int fib(int n) {
        if (n < 2) {
          return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

Dynamic Programming 的效能會比遞迴法好滿多。