Quy Hoạch Động (Dynamic Programming) Bài Toán Dãy Con Tăng Dài Nhất (Longest Increasing Subsequence)
Thời gian đọc: 7 phút
Thời gian đọc: 7 phút
Quy hoạch động (Dynamic Programming – DP) là một kỹ thuật tối ưu hóa được sử dụng để giải các bài toán có tính chất lặp lại, bằng cách chia nhỏ bài toán lớn thành các bài toán con nhỏ hơn. Quy hoạch động tận dụng kết quả của các bài toán con đã được giải trước đó để tránh tính toán lại, từ đó giảm thiểu thời gian thực thi.
Quy hoạch động thường được sử dụng trong các bài toán tối ưu hóa và các bài toán có cấu trúc con tối ưu (optimal substructure) và tính chất lặp lại (overlapping subproblems). Kỹ thuật này thường được áp dụng khi giải các bài toán như dãy con tăng dài nhất, bài toán xếp ba lô (knapsack problem), bài toán đường đi ngắn nhất, v.v.
Quy hoạch động giải quyết các bài toán thông qua ba bước chính:
Nếu bài toán có thể được chia thành các bài toán con độc lập mà giải pháp cho bài toán lớn có thể được xây dựng từ lời giải của các bài toán con, ta có cấu trúc con tối ưu.
Nếu các bài toán con lặp lại và có thể được giải quyết nhiều lần, thay vì tính toán lại mỗi khi cần, ta sẽ lưu trữ kết quả của các bài toán con để sử dụng lại sau này. Điều này giúp tiết kiệm thời gian và công sức.
Có hai cách tiếp cận trong quy hoạch động:
Bài toán dãy con tăng dài nhất (LIS) yêu cầu tìm độ dài của dãy con dài nhất trong một dãy số, sao cho các phần tử của dãy con đó là tăng dần theo thứ tự.
Cho một dãy số: [10, 22, 9, 33, 21, 50, 41, 60, 80], độ dài của dãy con tăng dài nhất là 6 với dãy con: [10, 22, 33, 50, 60, 80].
Gọi dp[i] là độ dài của dãy con tăng dài nhất kết thúc tại vị trí i. Khi đó:
dp[i] = max(dp[j]) + 1 với mọi j < i và arr[j] < arr[i]
Công thức này có nghĩa là nếu phần tử ở vị trí i lớn hơn phần tử ở vị trí j và dp[j] là độ dài của dãy con tăng dài nhất tại j, thì ta có thể mở rộng dãy con đó bằng phần tử i.
function longestIncreasingSubsequence($arr) {
$n = count($arr);
// Mảng dp dùng để lưu trữ độ dài của LIS kết thúc tại mỗi vị trí
$dp = array_fill(0, $n, 1);
// Duyệt qua từng phần tử trong mảng
for ($i = 1; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
if ($arr[$i] > $arr[$j] && $dp[$i] < $dp[$j] + 1) {
$dp[$i] = $dp[$j] + 1;
}
}
}
// Tìm giá trị lớn nhất trong mảng dp, chính là độ dài của LIS
$maxLIS = 0;
for ($i = 0; $i < $n; $i++) {
if ($maxLIS < $dp[$i]) {
$maxLIS = $dp[$i];
}
}
return $maxLIS;
}
$arr = [10, 22, 9, 33, 21, 50, 41, 60, 80];
echo "Độ dài của dãy con tăng dài nhất là: " . longestIncreasingSubsequence($arr);
dp: Ban đầu, mảng dp được khởi tạo với giá trị 1 cho mọi phần tử, vì mỗi phần tử riêng lẻ luôn tạo thành một dãy con tăng dài nhất có độ dài ít nhất là 1.i, kiểm tra tất cả các phần tử trước nó (j). Nếu arr[i] > arr[j] và dãy con tăng tại j có thể mở rộng bằng i, thì cập nhật dp[i] = dp[j] + 1.dp: Kết quả cuối cùng là giá trị lớn nhất trong mảng dp, tương ứng với độ dài của dãy con tăng dài nhất.
Độ dài của dãy con tăng dài nhất là: 6
dp để lưu trữ kết quả.Bài toán LIS có thể được tối ưu hóa xuống O(n log n) bằng cách sử dụng một cấu trúc dữ liệu tìm kiếm nhị phân để duy trì dãy con tăng tạm thời. Tuy nhiên, cách tiếp cận này phức tạp hơn và sẽ không được trình bày trong bài viết này.
Quy hoạch động là một kỹ thuật quan trọng và mạnh mẽ trong giải thuật, đặc biệt hữu ích khi giải quyết các bài toán có cấu trúc con tối ưu và tính chất lặp lại. Bằng cách lưu trữ và tái sử dụng kết quả của các bài toán con, quy hoạch động giúp tối ưu hóa hiệu suất và giảm thiểu thời gian thực thi.
Trong bài viết này, chúng ta đã tìm hiểu về quy hoạch động thông qua các bước giải bài toán và ví dụ cụ thể bằng PHP. Với khả năng áp dụng trong nhiều bài toán tối ưu hóa, việc hiểu và thành thạo kỹ thuật quy hoạch động sẽ giúp bạn giải quyết nhiều vấn đề phức tạp một cách hiệu quả.
