Số Fibonacci là những số sao cho mọi số trong chuỗi sau hai số đầu tiên là tổng của hai số đứng trước. Chuỗi bắt đầu bằng 1, 1. Ví dụ -
1, 1, 2, 3, 5, 8, 13, 21, 34, ….
Chúng ta có thể viết một chương trình để tạo thứ n như sau -
functionfibNaive(n) {
if (n<= 1) return n;
returnfibNaive(n - 1) + fibNaive(n - 2);
} Bạn có thể kiểm tra điều này bằng cách sử dụng -
console.log(fibNaive(7)); console.log(fibNaive(8)); console.log(fibNaive(9)); console.log(fibNaive(4));
Điều này sẽ cung cấp đầu ra -
13 21 34 3
Hãy để chúng tôi xem xét cách các lệnh gọi hàm này đang thực sự diễn ra như thế nào -
/** * f(5) * / \ * f(4) f(3) * / \ / \ * f(3) f(2) f(2) f(1) * / \ .......... * f(2) f(1).......... */
Khi chúng tôi thực hiện cuộc gọi đến f (5), chúng tôi sẽ gọi f (2) gần 4 lần và nó sẽ chạy cùng một mã lặp đi lặp lại 4 lần. Đây là một trường hợp của một vấn đề con chồng chéo. Hãy thử chạy chức năng đó trong 500. Bạn sẽ gặp khó khăn vì tất cả các cuộc gọi này sẽ mất rất nhiều thời gian.
Khi chúng ta cần số Fibonacci thứ 5, chúng ta chỉ cần các số Fibonacci thấp hơn một lần nhưng chúng ta tính toán chúng nhiều lần hơn thế. Chúng ta có thể giảm việc tính toán dư thừa này nếu thay vào đó chúng ta chỉ lưu trữ các giá trị đã tính toán ở đâu đó. Đây là điểm mấu chốt của lập trình động.
Tính toán một lần và sử dụng lại sau.
Hãy xem cách triển khai hàm fib được ghi nhớ.
letfibStore = {};
functionfibDP(n) {
if (n<= 1) return n;
if (fibStore[n]) {
returnfibStore[n];
}
fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
returnfibStore[n];
} Bây giờ chúng tôi đang sử dụng một cửa hàng, fibStore để theo dõi các giá trị mà chúng tôi đã tính toán. Điều này làm giảm các phép tính thừa quá mức và giữ cho chức năng hoạt động hiệu quả.
Bạn có thể kiểm tra điều này bằng cách sử dụng -
console.log(fibDP(7)); console.log(fibDP(8)); console.log(fibDP(9)); console.log(fibDP(4));
Điều này sẽ cung cấp đầu ra -
13 21 34 3
Bạn thậm chí có thể kiểm tra điều này để biết các giá trị lớn.