LeetCode 75 Level 1 - Day 10 Dynamic Programming

509. 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,

Given , calculate .

預設函數

int fib(int n){

}

題目限制

• 0 <= n <= 30

解題過程及程式碼

本題是 Dynamic Programming的第一題，題目要求出費氏數列 (費波那契數列)第 n 項的值，最直覺的做法，依題目公式寫成程式碼，但是不停的呼叫函數會較慢，時間複雜度。

• 遞迴程式碼

  int fib(int n){
      if (n == 1) {
          return 1;
      } else if (n > 1) {
          return fib(n - 1) + fib(n - 2);  /* F(n) = F(n - 1) + F(n - 2) */
      } else {
          return 0;
      }
  }
  
  

• 使用陣列將已經計算過的結果存入，時間複雜度

  int fib(int n){
      int f[31];
  
      f[0] = 0;
      f[1] = 1;
      for (int i=2; i<=n; ++i) {
          f[i] = f[i-1] + f[i-2];
      }
      return f[n];
  }
  

• 再來是不使用陣列的迴圈計算

  int fib(int n){
      int f = 1;
      int fn1 = 0, fn2 = 1;
  
      for (int i=2; i<=n; ++i) {
          fn2 = f;
          f = f + fn1;
          fn1 = fn2;
      }
  
      if (n == 0) return 0;
      else if (n == 1) return 1;
      else return f;
  }
  

今天到這裡，謝謝大家!