ลำดับฟีบอนัชชีใน JavaScript

Fibonacci numbers คือตัวเลขที่ทุกตัวหลังจากสองตัวแรกเป็นผลรวมของสองตัวก่อนหน้า เริ่มต้นที่ 1, 1 ตัวอย่าง:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

เราสามารถเขียนโปรแกรมสร้างตัวที่ n ได้ดังนี้:

function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

ทดสอบได้ดังนี้:

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

ผลลัพธ์:

13
21
34
3

มาดูว่า function calls เกิดขึ้นอย่างไร:

f(5)
 / \
f(4) f(3)
 / \ / \
f(3) f(2) f(2) f(1)
 / \ ...........
f(2) f(1)..........

เวลาเรียก f(5) เราจะเรียก f(2) เกือบ 4 ครั้ง รันโค้ดซ้ำ 4 ครั้ง นี่คือ overlapping subproblem ลองรัน f(500) จะค้างเพราะ calls เยอะมาก

ตอนต้องการ 5th Fibonacci number เราต้องการ lower Fibonacci numbers แค่ครั้งเดียวแต่คำนวณซ้ำหลายครั้ง เราลด redundant computation ได้ถ้าเก็บค่าที่คำนวณแล้วไว้ นี่คือหัวใจของ dynamic programming

คำนวณครั้งเดียว ใช้ซ้ำทีหลัง

มาดู memoized implementation:

let fibStore = {};
function fibDP(n) {
  if (n <= 1) return n;
  if (fibStore[n]) {
    return fibStore[n];
  }
  fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
  return fibStore[n];
}

ตอนนี้เราใช้ store (fibStore) เก็บค่าที่คำนวณแล้ว ลด redundant computations ทำให้ฟังก์ชันมีประสิทธิภาพ

ทดสอบได้ดังนี้:

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

ผลลัพธ์:

13
21
34
3

คุณสามารถทดสอบค่ามากได้เช่นกัน