Đề bài: Cho N ô vuông sắp xếp từ 1->N, và có chú ếch đang đứng ở ô đầu. Mỗi lượt, chú ếch có thể nhảy lên 1 hoặc 2 ô tiếp theo. Tìm số cách để chú ếch này đi đến ô thứ N.

P1: Phân tích

Với N=4, có các lời giải:

1->2->3->4

1->2->4

1->3->4

Với một số những người lập trình mới, đề bài này có thể khá là khê =))

Tuy nhiên, nếu nhìn 1 cách kỹ càng, sẽ dễ đặt câu hỏi là "Ủa, đây là dãy Fibonacci mà??"

Nếu bạn nghĩ thế, chúc mừng, bạn đã đúng!

P2: Làm thôi!

Mình tạo 2 lời giải nhé

LG1: Đệ quy

Cách này độ phức tạp 2^n, ko tối ưu lắm đâu nhé!

Click me for code!

LG2: Quy hoạch động

Nếu bạn chưa biết, quy hoạch động là thuật toán thần thánh để giảm thiểu thời gian cần thiết cho 1 lời giản đệ quy!

Phương pháp này dùng để giải nếu phải tính đi tính lại các phần tử nhiều lần, thì mình tính sẵn phần tử và lưu nó vào trong 1 mảng

Nếu cần tính lại thì cách đệ quy sẽ tính lại, còn quy hoạch động thì có sẵn biến rồi

Code luôn nhé!

CLick me for code!

Độ phức tạp từ O(2^n) xuống O(n) rồi! Tối ưu nhỉ

* *Nếu bạn thấy bài đọc này hay, thì cảm ơn bạn đã đọc. Mong bạn học được thêm nhiều điều hữu ích! **