Cài đặt thuật toán Longest Increasing Subsequence trong lập trình

Trong lập trình, việc tìm kiếm giải pháp cho bài toán chuỗi con tăng dài nhất (Longest Increasing Subsequence - LIS) là một vấn đề phổ biến và thử thách trong lĩnh vực thuật toán. Bài toán này đòi hỏi phải xác định chuỗi con (subsequence) dài nhất mà các phần tử trong chuỗi con đó tăng dần theo chỉ số từ một dãy số ban đầu. Dưới đây, chúng ta sẽ tìm hiểu cách cài đặt thuật toán này với hai phương pháp phổ biến: phương pháp sử dụng lập trình động (Dynamic Programming) và phương pháp sử dụng Cây Tìm kiếm Nhị phân (Binary Search).

Phương pháp lập trình động (Dynamic Programming)

Lập trình động là một trong những cách tiếp cận dễ hiểu và phổ biến để giải quyết bài toán LIS. Mặc dù phương pháp này có độ phức tạp thời gian là O(n^2), nhưng nó vẫn thường được sử dụng vì tính đơn giản và dễ triển khai.

Bước thực hiện:

1. Tạo mảng dp: Khởi tạo một mảng dp có cùng kích thước với mảng đầu vào, trong đó dp[i] lưu trữ độ dài của chuỗi con tăng dài nhất kết thúc tại chỉ số i.
2. Khởi tạo giá trị ban đầu: Gán tất cả các phần tử của mảng dp bằng 1, vì một phần tử độc lập được xem như là một chuỗi con có độ dài 1.
3. Tính toán giá trị của mảng dp:
   • Duyệt qua từng phần tử của mảng đầu vào từ trái sang phải.
   • Với mỗi phần tử tại vị trí i, kiểm tra tất cả các phần tử trước đó (tức là từ 0 đến i-1).
   • Nếu phần tử trước nhỏ hơn phần tử hiện tại và dp[i] nhỏ hơn dp[j] + 1, thì cập nhật dp[i] bằng dp[j] + 1.
4. Xác định kết quả cuối cùng: Độ dài chuỗi con tăng dài nhất là giá trị lớn nhất trong mảng dp.

Ví dụ mã cài đặt bằng Python:

def LIS(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
    return max(dp)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print("Độ dài của chuỗi con tăng dài nhất là:", LIS(arr))

Phương pháp sử dụng Cây Tìm kiếm Nhị phân (Binary Search)

Phương pháp này phức tạp hơn một chút so với lập trình động nhưng tiết kiệm thời gian hơn với độ phức tạp là O(n log n).

Bước thực hiện:

1. Tạo danh sách phụ tail: Danh sách tail này sẽ lưu giữ các phần tử sao cho tail[i] là phần tử nhỏ nhất có thể kết thúc một chuỗi con tăng dần có độ dài i+1.
2. Duyệt qua mảng đầu vào: Với mỗi phần tử arr[i], sử dụng phương pháp tìm kiếm nhị phân để xác định vị trí chèn (insert position) trong tail.
   • Nếu phần tử arr[i] lớn hơn tất cả các phần tử trong tail, thêm arr[i] vào cuối danh sách.
   • Nếu không, thay thế phần tử tìm được bằng arr[i] để giữ cho danh sách tail luôn ổn định.
3. Kết quả cuối cùng: Độ dài của danh sách tail chính là độ dài của chuỗi con tăng dài nhất.

Ví dụ mã cài đặt bằng Python:

import bisect

def LIS(arr):
    tail = []
    for num in arr:
        pos = bisect.bisect_left(tail, num)
        if pos < len(tail):
            tail[pos] = num
        else:
            tail.append(num)
    return len(tail)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print("Độ dài của chuỗi con tăng dài nhất là:", LIS(arr))

Kết luận

Cả hai phương pháp cài đặt trên đều phục vụ mục đích tìm ra độ dài của chuỗi con tăng dài nhất từ một dãy số cho trước, tuy nhiên, chúng có cách thực hiện và độ phức tạp khác nhau. Phương pháp lập trình động thích hợp cho những ai mới bắt đầu và muốn hiểu sâu về cách xây dựng thuật toán. Ngược lại, phương pháp sử dụng Cây Tìm kiếm Nhị phân thích hợp cho những bài toán lớn hơn với yêu cầu độ phức tạp thời gian thấp hơn. Hy vọng những hướng dẫn và mã nguồn trên sẽ giúp bạn triển khai thành công thuật toán này trong các bài toán lập trình của mình.