Trong khi lập trình chắc hẳn chúng ta đã từng tiếp cận với quy hoạch động và các bài toán liên quan đến thằng này thường khá khó "nhằn" 😄. Bài viết này sẽ tìm hiểu một phương pháp để giúp chúng ta có thể dễ dàng hơn trong việc "xử đẹp" những bài toán liên quan đến nó.

Phương pháp "FAST" này là gì vậy?

"FAST" ở đây thực ra là tên các chữ cái lấy ra từ các bước trong phương pháp này trong tiếng anh. Mình có "việt sắp" nó ra. Các bước đó là:

  • Tìm giải pháp đầu tiên (First Solution)
  • Phân tích giải pháp đầu tiên vừa tìm ra (Analyze the first solution)
  • Tìm các đoạn lặp của chúng (Identify the Subproblems)
  • Chuyển về dạng của quy hoạch động(Turn the solution around)

Và để cho đơn giản và giải thích cho các bước của phương pháp này mình sẽ sử dụng ví dụ về số Fibonacci. Bài toán như sau: Cho 1 số nguyên n. Viết một hàm để trả về số Fibonacci số n. OK let's go!

Step1: First solution

Bước đầu tiên trong phương pháp này là tìm ra giải pháp đầu tiên. Nhớ lại về số Fibonacci

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) // định nghĩa
fibonacci(0) = 0, fibonacci(1) = 1 // các điều kiện cơ sở

Nhìn vào định nghĩa trên ta có thể dễ dàng tìm ra "first solution" của nó bằng cách viết một hàm đệ quy

public int fibonacci(int n) {
    if(n<2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

OK xong rất dễ phải không 😄 và chúng ta nghĩ rằng done, "easy vồn" 😄 Nhưng sự thật là giải pháp trên trong thuật ngữ người ta gọi là "Naive method" (mình dịch là phương pháp ngây thơ. Móa 😦 ) Hãy chuyển sang bước 2 để xem tại sao nó lại là "ngây thơ" nhé.

Step 2: Analyze the first solution

Hãy cùng phân tích phương pháp ở bước 1 vừa tạo ra. Hãy thử chạy nó với n = 4 xem điều gì xảy ra.

fibonacci(4) = fibonacci(3) + fibonacci(2); // bước 1
// tiếp theo các hàm fibonacci(3) và fibonacci(2) sẽ được tính theo công thức đệ quy 
fibonacci(3) = fibonacci(2) + fibonacci(1);  // tại đây hàm fibonacci(2) lại được gọi và sẽ được thực hiện lại mặc dù tại bước 1 đã được tính rồi 
fibonacci(2) = fibonacci(1) + fibonacci(0); 
...
cho đến khi gặp "base solution" tại n = 0 hoặc n = 1 sẽ trả về kết quả tương ứng là fibonacci(0) = 0, fibonacci(1) = 1

Chúng ta có thể tính được "run time" của phương pháp này. Có thể thấy độ sâu của cây khi ta gọi đệ quy là n, với mỗi lần đệ quy sẽ gọi 2 hàm. Vậy ta có thể tính toán được số lần gọi là 2^0 + 2^1 + ... + 2^n-1 rút gọn thành o(2^n) (đúng là "ngây thơ" thật 😦 ) Hãy cùng sang bước 3 để cùng xem các bước lặp của phương pháp này.

Step 3: Find the subproblems

Tại mỗi bước gọi ta chia ra được thành 2 subproblems, sau đó ta sẽ dùng kết quả của các subproblems này để tính toán cho kết quả cuối cùng.

 với mỗi lần gọi fibonacci(n) sẽ có 2 subproblems là fibonacci(n-1) và fibonacci(n-2)
 Vớii toán Fibonacci này ta có thể dễ dàng tìm được subproblems của nó, tuy nhiên với nhiều bài việc tìm ra nó có thể sẽ phức tạp hơn.

ví dụ

fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)

Có thể thấy fibonacci(2) được gọi trong cả 2 lần và mỗi lần phải xử lý lại, nên ta có th