- Giới thiệu về Lập trình động
Lập trình động (tiếng Anh: Dynamic programming, viết tắt là DP) là một phương pháp giải quyết các vấn đề phức tạp bằng cách chia nhỏ chúng thành các vấn đề con đơn giản hơn. Phương pháp này thường được áp dụng trong toán học, khoa học quản lý, khoa học máy tính, kinh tế học và sinh tin học. Lập trình động đặc biệt hữu ích cho các vấn đề có tính chất con vấn đề chồng lấn và cấu trúc con tối ưu.
1.1 Vấn đề con chồng lấn và Cấu trúc con tối ưu
1.1.1 Vấn đề con chồng lấn
Vấn đề con chồng lấn là những vấn đề con xuất hiện nhiều lần trong quá trình giải quyết vấn đề lớn. Đặc điểm này cho phép chúng ta lưu kết quả của các vấn đề con đã giải để tránh tính toán lại, từ đó tăng hiệu suất thuật toán.
1.1.2 Cấu trúc con tối ưu
Cấu trúc con tối ưu có nghĩa là giải pháp tối ưu cho vấn đề lớn có thể được xây dựng từ giải pháp tối ưu của các vấn đề con. Nói cách khác, giải pháp tối ưu của vấn đề lớn bao gồm giải pháp tối ưu của các vấn đề con. Đây là một trong những đặc tính quan trọng của lập trình động.
1.1.3 Ví dụ minh họa
Ví dụ, xét một dãy gồm n phần tử, ta cần tìm dãy con tăng dài nhất (LIS, Longest Increasing Subsequence). Vấn đề này có tính chất cấu trúc con tối ưu. Nếu biết dãy con tăng dài nhất của một dãy, khi thêm một phần tử vào cuối dãy, sẽ có hai trường hợp:
- Nếu phần tử này lớn hơn phần tử cuối cùng của dãy con tăng hiện tại, thì dãy con tăng mới sẽ là dãy cũ cộng thêm phần tử này, độ dài tăng lên 1;
- Nếu phần tử này nhỏ hơn hoặc bằng phần tử cuối cùng của dãy con tăng hiện tại, thì dãy con tăng không thay đổi.
Do đó, giải pháp tối ưu cho vấn đề mới có thể được xây dựng từ giải pháp của các vấn đề con đã biết.
1.2 Tư tưởng cốt lõi của Lập trình động
Tư tưởng cốt lõi nhất của lập trình động là chia nhỏ vấn đề, ghi nhớ các kết quả đã tính toán trước đó để tránh tính toán trùng lặp.
Xét một ví dụ đơn giản:
A: "1+1+1+1+1+1+1+1 = ?" A: "Kết quả của biểu thức trên là bao nhiêu?" B: Tính toán "8" A: "Nếu thêm '1+' vào bên trái của biểu thức trên thì sao?" A: "Giá trị của biểu thức mới là bao nhiêu?" B: Nhanh chóng trả lời "9" A: "Tại sao bạn trả lời nhanh thế?" A: "Chỉ cần thêm 1 vào kết quả 8 là được!" A: "Vì vậy bạn không cần tính lại, vì bạn đã nhớ kết quả của biểu thức đầu tiên! Thuật toán lập trình động cũng có thể được hiểu là 'ghi nhớ các kết quả đã tính để tiết kiệm thời time'"
1.3 Vấn đề con ếch nhảy lên bậc thang
Đề bài gốc trên LeetCode: Một con ếch có thể nhảy 1 bước hoặc 2 bước mỗi lần. Hỏi con ếch có bao nhiêu cách để nhảy lên một bậc thăng 10 bậc?
1.3.1 Phân tích giải pháp
Cơ bản: Lập trình động giải quyết các vấn đề nhỏ trước, sau đó sử dụng tính chất chồng lấn để dần dần giải quyết các vấn đề lớn hơn, từ f(1) đến f(10). Đây là phương pháp từ dưới lên.
Cụ thể hơn, giả sử số cách nhảy lên bậc thang thứ n là f(n):
- Khi chỉ có 1 bậc thang, chỉ có 1 cách nhảy, tức f(1) = 1;
- Khi có 2 bậc thang, có 2 cách nhảy. Cách 1 là nhảy thẳng 2 bậc. Cách 2 là nhảy 1 bậc rồi lại nhảy 1 bậc nữa. Tức f(2) = 2;
- Khi có 3 bậc thang, có 2 cách nhảy. Cách 1 là từ bậc 1 nhẳng thẳng 2 bậc lên bậc 3. Cách 2 là từ bậc 2 nhảy 1 bậc lên bậc 3. Tức f(3) = f(1) + f(2);
- Để nhảy lên bậc 4, có thể nhảy từ bậc 3 rồi nhảy 1 bậc lên, hoặc nhảy từ bậc 2 rồi nhẳng thẳng 2 bậc lên. Tức f(4) = f(2) + f(3);
Từ đây, ta có công thức:
f(1) = 1; f(2) = 2; f(3) = f(1) + f(2); f(4) = f(2) + f(3); ... f(10) = f(8) + f(9); Hay f(n) = f(n-2) + f(n-1).
Các đặc trưng của lập trình động trong bài toán này:
- Cấu trúc con tối ưu: f(n-1) và f(n-2) là các cấu trúc con tối ưu của f(n).
- Vấn đề con chồng lấn: Ví dụ, f(10) = f(9) + f(8), f(9) = f(8) + f(7), thì f(8) là vấn đề con bị tính toán nhiều lần.
- Phương trình chuyển trạng thái: f(n) = f(n-1) + f(n-2) được gọi là phương trình chuyển trạng thái.
- Điều kiện biên: f(1) = 1, f(2) = 2 là các điều kiện biên.
1.3.2 Code giải pháp
Ý tưởng code như sau:
Code thực hiện:
class GiaiPhap {
public:
int soCachNhay(int n) {
int mangQuyHoach[101] = {0};
int modulo = 1000000007;
mangQuyHoach[0] = 1;
mangQuyHoach[1] = 1;
mangQuyHoach[2] = 2;
for (int i = 3; i <= n; i++) {
mangQuyHoach[i] = mangQuyHoach[i - 1] + mangQuyHoach[i - 2];
mangQuyHoach[i] %= modulo;
}
return mangQuyHoach[n] % modulo;
}
};
Phương pháp này có độ phức tạp không gian là O(n), nhưng ta có thể tối ưu hơn. Quan sát thấy rằng f(n) chỉ phụ thuộc vào hai số trước đó, vì vậy ta chỉ cần hai biến a và b để lưu trữ là đủ, giúp giảm độ phức tạp không gian xuống O(1).
Code thực hiện:
class GiaiPhap {
public:
int soCachNhay(int n) {
if (n < 2) {
return 1;
}
if (n == 2) {
return 2;
}
int a = 1;
int b = 2;
int tam = 0;
for (int i = 3; i <= n; i++) {
tam = (a + b) % 1000000007;
a = b;
b = tam;
}
return tam;
}
};
2. Khuôn mẫu giải quyết bài toán Lập trình động
2.1 Tư tưởng cốt lõi
Tư tưởng cốt lõi của lập trình động là chia nhỏ vấn đề, ghi nhớ kết quả đã tính toán để tránh tính toán trùng lặp. Các bài toán lập trình động thường được giải từ dưới lên. Dựa vào bài toán con ếch nhảy, ta có thể tổng kết các bước giải quyết bài toán lập trình động:
- Phân tích toàn bộ các khả năng
- Xác định điều kiện biên
- Tìm quy luật, xác định cấu trúc con tối ưu
- Viết phương trình chuyển trạng thái
2.1.1 Phân tích ví dụ
- Phân tích toàn bộ các khả năng (1) Khi có 1 bậc thang, có 1 cách nhảy, f(1) = 1 (2) Khi có 2 bậc thang, có 2 cách nhảy: nhảy thẳng 2 bậc, hoặc nhảy 1 bậc rồi lại nhảy 1 bậc. Tức f(2) = 2 (3) Khi có 3 bậc thang, để nhảy lên bậc 3, có thể nhảy từ bậc 2 rồi nhảy 1 bậc lên, hoặc nhảy từ bậc 1 rồi nhẳng thẳng 2 bậc lên. Vậy f(3) = f(2) + f(1) = 3 (4) Khi có 4 bậc thang, để nhảy lên bậc 4, có thể nhảy từ bậc 3 rồi nhảy 1 bậc lên, hoặc nhảy từ bậc 2 rồi nhẳng thẳng 2 bậc lên. Vậy f(4) = f(3) + f(2) = 5 (5) Khi có 5 bậc thang...
- Xác định điều kiện biên Qua phân tích, khi số bậc thang là 1 hoặc 2, ta có thể xác định số cách nhảy của ếch một cách rõ ràng. f(1) = 1, f(2) = 2, khi n >= 3, đã xuất hiện quy luật f(3) = f(2) + f(1) = 3. Do đó, f(1) = 1, f(2) = 2 là điều kiện biên của bài toán.
- Tìm quy luật, xác định cấu trúc con tối ưu Khi n >= 3, đã xuất hiện quy luật f(n) = f(n-1) + f(n-2). Do đó, f(n-1) và f(n-2) được gọi là cấu trúc con tối ưu của f(n). Cấu trúc con tối ưu là gì?
Một bài toán lập trình động thực chất là một bài toán quy hồi. Giả sử kết quả của quyết định hiện tại là f(n), thì cấu trúc con tối ưu chính là việc đảm bảo f(n-k) là tối ưu, đặc tính này cho phép chuyển trạng thái đến n là tối ưu và không phụ thuộc vào các quyết định sau, tức là đảm bảo các quyết định sau có thể yên tâm sử dụng giải pháp cục bộ tối ưu của các bước trước.
- Từ 3 bước trên, phân tích toàn bộ, xác định điều kiện biên, cấu trúc con tối ưu, ta có thể suy ra phương trình chuyển trạng thái:
3. Ví dụ bài toán
3.1 Dãy con tăng dài nhất
3.1.1. Phân tích toàn bộ các khả năng:
- Khi nums chỉ có 10, dãy con dài nhất là [10], độ dài 1.
- Khi nums thêm 9, dãy con dài nhất là [10] hoặc [9], độ dài 1.
- Khi nums thêm 2, dãy con dài nhất là [10] hoặc [9] hoặc [2], độ dài 1.
- Khi nums thêm 5, dãy con dài nhất là [2, 5], độ dài 2.
- Khi nums thêm 3, dãy con dài nhất là [2, 5] hoặc [2, 3], độ dài 2.
- Khi nums thêm 7, dãy con dài nhất là [2, 5, 7] hoặc [2, 3, 7], độ dài 3. ...
- Khi nums thêm phần tử 18, dãy con tăng dài nhất là [2,5,7,101] hoặc [2,3,7,101] hoặc [2,5,7,18] hoặc [2,3,7,18], độ dài là 4.
3.1.2 Xác định điều kiện biên
Đối với mỗi phần tử trong mảng nums, khi chưa bắt đầu duyệt tìm, dãy con tăng dài nhất ban đầu của chúng là chính chúng với độ dài 1.
3.1.3 Tìm quy luật, xác định cấu trúc con tối ưu
Qua phân tích trên, ta có thể nhận thấy một quy luật:
Dãy con tăng kết thúc tại nums[i], chỉ cần tìm dãy con kết thúc tại nums[j] với nums[j] < nums[i], rồi thêm nums[i] vào. Rõ ràng, có thể tạo ra nhiều dãy con mới, ta chọn dãy dài nhất, đó chính là dãy con tăng dài nhất kết thúc tại nums[i].
Từ đó ta có cấu trúc con tối ưu:
Dãy con tăng dài nhất kết thúc tại nums[i] = max(Dãy con tăng dài nhất kết thúc tại nums[j]) + 1; với 0