Bài 10.2 - Longest Increasing Subsequence (LIS) với Python

LIS (Longest Increasing Subsequence) là một trong những bài toán quy hoạch động nổi tiếng, thường xuất hiện trong phỏng vấn và thi lập trình.

Mục tiêu:
Tìm độ dài của dãy con tăng dài nhất trong một dãy số.

Ví dụ

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Giải thích: Dãy con tăng dài nhất là [2, 3, 7, 101].

1. Cách 1 – Dùng Dynamic Programming (O(n²))

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n  # Mỗi phần tử ít nhất là 1

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)
Ví dụ:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))  # Output: 4

Mỗi phần tử dp[i] lưu độ dài LIS kết thúc tại i.

2. Cách 2 – Tối ưu với nhị phân (O(n log n))

import bisect

def length_of_lis_binary(nums):
    sub = []

    for num in nums:
        i = bisect.bisect_left(sub, num)
        if i == len(sub):
            sub.append(num)
        else:
            sub[i] = num

    return len(sub)
Ví dụ:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis_binary(nums))  # Output: 4

sub không phải là dãy LIS thật sự, nhưng độ dài của nó chính là kết quả.

3. So sánh 2 cách

Cách giải Độ phức tạp Ưu điểm Nhược điểm
DP (O(n²)) Chậm hơn Dễ hiểu, dễ debug Không hiệu quả với n lớn
Nhị phân (O(n log n)) Nhanh Rất tối ưu với dữ liệu lớn Khó lấy lại dãy LIS

4. Muốn truy vết lại dãy LIS?

def reconstruct_lis(nums):
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j

    # Tìm chỉ số có LIS dài nhất
    lis_len = max(dp)
    index = dp.index(lis_len)

    # Truy vết ngược
    lis = []
    while index != -1:
        lis.append(nums[index])
        index = prev[index]

    return lis[::-1]
Ví dụ:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(reconstruct_lis(nums))  # Output: [2, 3, 7, 101]

Dùng thêm mảng prev để truy vết đường đi.

Tổng kết

  • LIS là bài toán hay để rèn tư duy quy hoạch động và tối ưu thuật toán.
  • Có thể bắt đầu với giải pháp O(n²), sau đó nâng cấp lên O(n log n) để học kỹ thuật nhị phân kết hợp mảng.
  • Khi cần in ra dãy LIS thực tế, hãy thêm mảng prev để truy vết.

Khóa học liên quan

Khoá học lập trình Python Giảm giá!
Ưu đãi có hạn
Khoá học lập trình Python
4.8 120 giờ
3300000 4500000
Học Ngay

Comments

There are no comments at the moment.