Tìm hiểu phương pháp học đệ quy, quy hoạch động và đồ thị

Phương pháp chung của quy hoạch động là dùng mảng hoặc ma trận để lưu giá trị trước đó (có ảnh hưởng đến kết quả sau). Như vậy, các dạng toán thường được sử dụng quy hoạch động là các dạng có tính chất như trên, kết quả của phần tử tiếp theo phụ thuộc vào (các) phần tử trước đó.

Để dùng QHĐ thì bài phải chia được thành nhiều bài nhỏ hơn và lời giải đúng sẽ là tổ hợp của lời giải những bài nhỏ. Hay nói cách khác là phải tìm cho ra công thức truy hồi.

Đa phần QHĐ là yêu cầu tối ưu (lớn/nhỏ nhất) nhưng có 1 số bài không phải (sách LMH). QHĐ nhiều bài cực troll muốn chia nhỏ ra không phải dễ.

Theo kinh nghiệm cùi bắp của mình:

Đệ quy và QHĐ đều là thứ này phụ thuộc vào cái kia, nhưng:

• Đệ quy: là những thứ không phải nghĩ gì nhiều, cứ viết rồi sẽ tới. Ta biết sự phụ thuộc giữa các hàm số f, nhưng ta chưa biết được những bước trước đó ta có cái gì, kiểu như đi giật lùi mà không có mắt ở sau gáy.

fibo(n):
    return fibo(n-1)+fibo(n-2) # rõ ràng không phải nghĩ gì, như định nghĩa

• Quy hoạch động: phải nghĩ, phải nhìn ra sự phụ thuộc, và ta buộc phải chú ý đến nó, giống như đi giật lùi mà có “mắt” để quan sát được chỗ nào đi được, chỗ nào không. QHĐ trong nhiều trường hợp hiệu quả hơn đệ quy (có 1 số bài có dạng đệ quy và QHĐ kết hợp).

fibo[n] = fibo[n-1]+fibo[n-2] # vẫn như ví dụ trên, nhưng ta nhìn ra sự phụ thuộc,
# ta chắc chắn rằng những thứ phụ thuộc (fibo(n-1) và fibo(n-2)) đã được tính toán,
# nên ta hoàn toàn có thể tin tưởng để tính fibo(n).

Mình chỉ cố gắng giải thích cho bạn ý nghĩa cơ bản và dễ nhất của QHĐ và đệ quy, còn áp dụng thế nào là tùy bài và do tư duy, kinh nghiệm làm bài tập của bạn nữa, cái này không thể nói rõ ràng được.

Còn đồ thị, hình của nó chính là 1 đống điểm và 1 đống đường nối giữa 1 số điểm. Bạn nên quan tâm đến 1 số khái niệm như bậc của đỉnh, đơn/đa đồ thị, cạnh lặp, cạnh vòng,… (những khái niệm chung nhất) và các thuật toán trên đồ thị. Còn các định lí về đồ thị thì rất ít khi phải quan tâm đến (trừ khi bạn thích đấu giải ACM).

Quy hoạch động thực sự không có phương pháp cụ thể để học đâu, bạn phải làm nhiều bài tập để hiểu được bản chất của nó, ngay cả những pro mà khi gặp quy hoạch động còn phải ngán nữa mà, phải hiểu được bản chất vấn đề từ cốt lõi nhỏ nhất thì mới làm được.

Đúng vậy, bản chất QHĐ còn có thể bị ẩn đi như vẽ đường phụ trong hình học ấy; lúc đó phải thêm tham số thì mới đúng là QHĐ và có big-O thấp. Nhưng ta phải bắt đầu từ cơ bản đã như sách LMH.

Thực ra giáo trình thiếu một chủ đề quan trọng là interval tree.