Tìm chuỗi con không giảm dài nhất

NỘI DUNG

Giới thiệu bài toán

Cho một dãy số nguyên, tìm chuỗi con dài nhất sao cho các phần tử trong chuỗi con đó tăng dần theo thứ tự từ trái sang phải. Chuỗi con tăng dần có thể không liên tiếp. với bài toán này chúng ta sử dụng thuật toán Dynamic Programming (DP)

Dynamic Programming (DP) là một kỹ thuật giải quyết bài toán tối ưu hóa. Đặc trưng của các bài toán tối ưu hóa là chúng có nhiều cách giải quyết, và một cách tối ưu hóa có thể được tìm thấy thông qua việc tìm kiếm và so sánh các cách giải quyết khác nhau. DP thường được sử dụng khi các bài toán có tính chất lặp lại, nghĩa là kết quả của một bài toán có thể được tính dựa trên kết quả của các bài toán con giống nhau nhỏ hơn. DP sử dụng các phép toán và lưu trữ kết quả trung gian để giải quyết các bài toán lớn hơn.

Các bước của thuật toán

Để giải quyết bài toán Longest Increasing Subsequence, ta có thể sử dụng thuật toán Dynamic Programming với các bước như sau:

Khởi tạo một mảng dp với độ dài bằng với độ dài của dãy số ban đầu, và mỗi phần tử trong mảng dp ban đầu được khởi tạo là 1.
Lặp qua từng phần tử của dãy số ban đầu, với mỗi phần tử ta lặp lại từ đầu đến vị trí hiện tại để tìm xem có thể tạo ra chuỗi con tăng dần dài hơn không.
Với mỗi phần tử trong lần lặp ở bước 2, ta so sánh với các phần tử trước đó (có vị trí nhỏ hơn phần tử hiện tại) để xác định xem có thể thêm phần tử này vào chuỗi con tăng dần hiện tại hay không. Nếu có thể, ta cập nhật giá trị của dp tại vị trí phần tử hiện tại bằng giá trị của dp tại vị trí phần tử trước đó cộng thêm 1.
Cuối cùng, ta lặp lại mảng dp và tìm giá trị lớn nhất trong mảng đó, đó chính là độ dài của chuỗi con tăng dần dài nhất.

Ví dụ về thuật toán

Cho dãy số 1 3 2 6 4 5 8 7. Ta sử dụng thuật toán Dynamic Programming như sau:

Khởi tạo mảng dp với [1, 1, 1, 1, 1, 1, 1, 1].
Với phần tử đầu tiên của dãy số (1), ta lặp lại từ đầu đến phần tử đó (không có phần tử nào để so sánh). Không có phần tử nào trước đó để thêm vào chuỗi con tăng dần, nên giá trị tại vị trí đầu tiên trong mảng dp vẫn là 1.
Với phần tử thứ hai của dãy số (3), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 1, không thể tạo thành chuỗi con tăng dần mới, nên giá trị tại vị trí thứ hai trong mảng dp vẫn là 1.
Với phần tử thứ ba của dãy số (2), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 1, không thể tạo thành chuỗi con tăng dần mới, nên giá trị tại vị trí thứ ba trong mảng dp vẫn là 1.

Với phần tử thứ tư của dãy số (6), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 2, và 2 cũng nhỏ hơn 6, nên ta có thể thêm phần tử này vào chuỗi con tăng dần hiện tại để tạo thành chuỗi con tăng dần mới dài hơn. Vì vậy, giá trị tại vị trí thứ tư trong mảng dp được cập nhật thành 2 (giá trị của dp tại vị trí 2 cộng thêm 1).
Với phần tử thứ năm của dãy số (4), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 2, không thể tạo thành chuỗi con tăng dần mới, nên giá trị tại vị trí thứ năm trong mảng dp vẫn là 1.
Với phần tử thứ sáu của dãy số (5), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 4, và 4 cũng nhỏ hơn 5, nên ta có thể thêm phần tử này vào chuỗi con tăng dần hiện tại để tạo thành chuỗi con tăng dần mới dài hơn. Vì vậy, giá trị tại vị trí thứ sáu trong mảng dp được cập nhật thành 2 (giá trị của dp tại vị trí 4 cộng thêm 1).
Với phần tử thứ bảy của dãy số (8), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 5, và 5 cũng nhỏ hơn 8, nên ta có thể thêm phần tử này vào chuỗi con tăng dần hiện tại để tạo thành chuỗi con tăng dần mới dài hơn. Vì vậy, giá trị tại vị trí thứ bảy trong mảng dp được cập nhật thành 3 (giá trị của dp tại vị trí 6 cộng thêm 1).
Với phần tử cuối cùng của dãy số (7), ta lặp lại từ đầu đến phần tử đó. Phần tử trước đó là 5, không thể tạo thành chuỗi con tăng dần mới, nên giá trị tại vị trí cuối cùng trong mảng dp vẫn là 3.

Sau khi kết thúc vòng lặp, giá trị tại vị trí cuối cùng trong mảng dp chính là độ dài của chuỗi con tăng dần dài nhất của dãy số ban đầu. Trong trường hợp này, giá trị này là 3.

Mô tả thuật toán dưới dạng bảng

Dưới đây là một bảng mô tả từng bước của bài toán LIS để giúp bạn có thể hiểu rõ hơn về thuật toán này.

Giả sử chúng ta có một mảng arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] và muốn tìm chuỗi con tăng dần dài nhất của nó.

Bước	i	arr[i]	dp	Giải thích
1	0	3	1	Khởi tạo mảng dp với giá trị 1 tại mỗi vị trí
2	1	1	1	Với i = 1, không có j nào nhỏ hơn i sao cho arr[j] < arr[i], vì vậy giá trị của dp[1] không thay đổi
3	2	4	2	Với i = 2, ta kiểm tra tất cả các j nhỏ hơn i. Có 2 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 0 và j = 2. Vì vậy, ta cập nhật giá trị của dp[2] thành max(dp[2], dp[0]+1) = 2
4	3	1	1	Với i = 3, không có j nào nhỏ hơn i sao cho arr[j] < arr[i], vì vậy giá trị của dp[3] không thay đổi
5	4	5	3	Với i = 4, ta kiểm tra tất cả các j nhỏ hơn i. Có 3 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 0, j = 2 và j = 3. Vì vậy, ta cập nhật giá trị của dp[4] thành max(dp[4], dp[0]+1, dp[2]+1, dp[3]+1) = 3
6	5	9	4	Với i = 5, ta kiểm tra tất cả các j nhỏ hơn i. Có 4 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 0, j = 2, j = 3 và j = 4. Vì vậy, ta cập nhật giá trị của dp[5] thành max(dp[5], dp[0]+1, dp[2]+1, dp[3]+1, dp[4]+1) = 4
7	6	2	1	Với i = 6, không có j nào nhỏ hơn i sao cho arr[j] < arr[i], vì vậy giá trị của dp[6] không thay đổi
8	6	9	3	Với i = 6, ta kiểm tra tất cả các j nhỏ hơn i. Chỉ có 1 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 4. Vì vậy, ta cập nhật giá trị của dp[6] thành max(dp[6], dp[4]+1) = 3
9	7	6	2	Với i = 7, ta kiểm tra tất cả các j nhỏ hơn i. Có 2 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 0 và j = 4. Vì vậy, ta cập nhật giá trị của dp[7] thành max(dp[7], dp[0]+1, dp[4]+1) = 2
10	8	5	2	Với i = 8, ta kiểm tra tất cả các j nhỏ hơn i. Có 3 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 0, j = 2 và j = 4. Vì vậy, ta cập nhật giá trị của dp[8] thành max(dp[8], dp[0]+1, dp[2]+1, dp[4]+1) = 2
11	9	3	1	Với i = 9, không có j nào nhỏ hơn i sao cho arr[j] < arr[i], vì vậy giá trị của dp[9] không thay đổi
12	10	5	2	Với i = 10, ta kiểm tra tất cả các j nhỏ hơn i. Có 3 vị trí j thỏa mãn điều kiện arr[j] < arr[i], đó là j = 0, j = 2 và j = 4. Vì vậy, ta cập nhật giá trị của dp[10] thành max(dp[10], dp[0]+1, dp[2]+1, dp[4]+1) = 2

Sau khi tính toán tất cả các giá trị của dp, giá trị lớn nhất trong dp chính là độ dài của chuỗi con tăng dần dài nhất. Trong ví dụ này, độ dài chuỗi con tăng dần dài nhất của mảng arr là 4 và chuỗi con tăng dần dài nhất là [3, 4, 5, 9].

Cài đặt thuật toán

Dưới đây là một ví dụ về việc sử dụng thuật toán LIS để tìm chuỗi con tăng dần dài nhất của một mảng:

def longest_increasing_subsequence(arr):
    n = len(arr)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    # Tìm giá trị lớn nhất trong mảng dp
    max_len = max(dp)
    
    # Tìm chuỗi con tăng dần dài nhất
    lis = []
    for i in range(n-1, -1, -1):
        if dp[i] == max_len:
            lis.append(arr[i])
            max_len -= 1
        if max_len == 0:
            break
    
    # Đảo ngược chuỗi con tăng dần dài nhất để trả về kết quả đúng
    lis.reverse()
    
    return lis

Ví dụ: Tìm chuỗi con tăng dần dài nhất của mảng [5, 2, 8, 6, 3, 6, 9, 7]

arr = [5, 2, 8, 6, 3, 6, 9, 7]
lis = longest_increasing_subsequence(arr)
print(lis) # Kết quả: [2, 3, 6, 9]

Trong ví dụ này, chuỗi con tăng dần dài nhất của mảng là [2, 3, 6, 9].

Đánh giá độ phức tạp của thuật toán

Độ phức tạp của thuật toán LIS là O(n^2) trong trường hợp tổng quát. Tuy nhiên, có thể cải thiện độ phức tạp của thuật toán bằng cách sử dụng các thuật toán tìm kiếm nhị phân để giảm thời gian duyệt mảng. Trong trường hợp tốt nhất, thuật toán có độ phức tạp là O(n log n).

Lập trình Python