Bài 26.2: Dãy con tăng dài nhất (LIS)

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ cùng nhau "mổ xẻ" một bài toán cực kỳ kinh điển và quan trọng trong lập trình thi đấu cũng như khoa học máy tính: Bài toán tìm Dãy con tăng dài nhất hay còn gọi là Longest Increasing Subsequence (LIS).

Đây không chỉ là một bài toán lý thuyết mà còn có rất nhiều ứng dụng thực tế trong các lĩnh vực như phân tích dữ liệu, tin sinh học, hay thậm chí là tối ưu hóa trong sản xuất. Nắm vững cách giải bài toán LIS sẽ mở ra cho bạn những góc nhìn mới về cách tiếp cận các vấn đề liên quan đến dãy và chuỗi.

Dãy con tăng dài nhất là gì?

Trước hết, chúng ta cần hiểu rõ các khái niệm.

Một dãy con (subsequence) của một dãy cho trước được tạo ra bằng cách xóa bỏ không hoặc nhiều phần tử khỏi dãy gốc mà không làm thay đổi thứ tự của các phần tử còn lại.
- Ví dụ: Dãy gốc là [10, 9, 2, 5, 3, 7, 101, 18]. Các dãy con có thể là [10, 2, 7], [9, 5, 3, 1], [10, 9, 2, 5, 3, 7, 101, 18] (chính nó), hoặc [] (dãy rỗng).
Một dãy tăng (increasing sequence) là một dãy mà mỗi phần tử (trừ phần tử đầu tiên) đều lớn hơn phần tử đứng ngay trước nó.
- Ví dụ: [2, 5, 7, 18, 101] là một dãy tăng. [10, 9, 2, 5] không phải là dãy tăng.
Dãy con tăng (increasing subsequence) là một dãy con của dãy gốc, đồng thời nó cũng là một dãy tăng.
- Ví dụ với dãy gốc [10, 9, 2, 5, 3, 7, 101, 18]:
  - [2, 5, 7, 18] là một dãy con tăng (được tạo từ các phần tử ở index 2, 3, 5, 7).
  - [3, 7, 101] là một dãy con tăng (index 4, 5, 6).
  - [2, 3, 7, 101] cũng là một dãy con tăng (index 2, 4, 5, 6).

Bài toán Dãy con tăng dài nhất (LIS) yêu cầu chúng ta tìm một dãy con tăng có độ dài lớn nhất từ dãy ban đầu.

Với dãy ví dụ [10, 9, 2, 5, 3, 7, 101, 18], các dãy con tăng có thể là: [2, 5, 7, 18] (độ dài 4) [2, 3, 7, 18] (độ dài 4) [2, 5, 7, 101] (độ dài 4) [2, 3, 7, 101] (độ dài 4) [2, 5, 101] (độ dài 3) ... Và còn nhiều dãy khác. Dễ thấy, độ dài LIS cho dãy này là 4.

Làm thế nào để tìm được độ dài này một cách hiệu quả? Chúng ta hãy cùng xem xét các phương pháp.

Phương pháp 1: Quy hoạch động (Dynamic Programming) - Độ phức tạp O(N^2)

Đây là phương pháp phổ biến và dễ tiếp cận nhất để giải bài toán LIS. Ý tưởng chính là xây dựng một mảng DP, trong đó mỗi phần tử lưu trữ độ dài của dãy con tăng dài nhất kết thúc tại vị trí đó.

Gọi arr là dãy đầu vào có N phần tử. Chúng ta sẽ tạo một mảng dp cùng kích thước N.

dp[i] sẽ lưu trữ độ dài của dãy con tăng dài nhất kết thúc bằng phần tử arr[i].

Để tính dp[i], chúng ta cần xem xét tất cả các phần tử arr[j] đứng trước arr[i] (tức là j < i). Nếu arr[j] < arr[i], thì arr[i] có thể được thêm vào cuối một dãy con tăng kết thúc tại arr[j] để tạo thành một dãy con tăng mới kết thúc tại arr[i]. Độ dài của dãy mới này sẽ là dp[j] + 1.

Để dp[i] có giá trị lớn nhất, chúng ta cần tìm giá trị dp[j] lớn nhất trong số tất cả các j < i thỏa mãn arr[j] < arr[i].

Công thức truy hồi sẽ là: dp[i] = 1 + max(dp[j]) với mọi 0 <= j < i sao cho arr[j] < arr[i]. Nếu không có j < i nào thỏa mãn arr[j] < arr[i] (ví dụ arr[i] là phần tử nhỏ nhất đứng sau nó), thì dãy con tăng dài nhất kết thúc tại arr[i] chỉ có mình nó, nên dp[i] = 1.

Giá trị khởi tạo: Mọi dp[i] ban đầu đều bằng 1 (vì mỗi phần tử arr[i] tự tạo thành một dãy con tăng độ dài 1).

Sau khi tính toán hết tất cả các giá trị dp[i] cho i từ 0 đến N-1, độ dài LIS của cả dãy gốc chính là giá trị lớn nhất trong mảng dp.

Hãy xem xét ví dụ arr = [10, 9, 2, 5, 3, 7, 101, 18]. N = 8.

dp[0] (cho arr[0] = 10): Không có phần tử nào trước nó. dp[0] = 1.
dp[1] (cho arr[1] = 9): arr[0] = 10. 10 không nhỏ hơn 9. Không có j < 1 thỏa mãn arr[j] < arr[1]. dp[1] = 1.
dp[2] (cho arr[2] = 2): arr[0] = 10, arr[1] = 9. Cả hai đều không nhỏ hơn 2. dp[2] = 1.
dp[3] (cho arr[3] = 5):
- j = 0: arr[0] = 10. 10 không nhỏ hơn 5.
- j = 1: arr[1] = 9. 9 không nhỏ hơn 5.
- j = 2: arr[2] = 2. 2 nhỏ hơn 5. dp[2] = 1. Có thể tạo dãy con tăng kết thúc bằng 5 có độ dài dp[2] + 1 = 1 + 1 = 2 (ví dụ: [2, 5]).
- Max dp[j] cho j < 3 và arr[j] < arr[3] là dp[2] = 1.
- dp[3] = 1 + dp[2] = 1 + 1 = 2.
dp[4] (cho arr[4] = 3):
- j = 0: arr[0] = 10 (không).
- j = 1: arr[1] = 9 (không).
- j = 2: arr[2] = 2. 2 < 3. dp[2] = 1. Có thể tạo [2, 3], độ dài dp[2]+1 = 2.
- j = 3: arr[3] = 5 (không).
- Max dp[j] cho j < 4 và arr[j] < arr[4] là dp[2] = 1.
- dp[4] = 1 + dp[2] = 1 + 1 = 2.
dp[5] (cho arr[5] = 7):
- j = 0: arr[0] = 10 (không).
- j = 1: arr[1] = 9 (không).
- j = 2: arr[2] = 2. 2 < 7. dp[2] = 1. Dãy: [2, 7].
- j = 3: arr[3] = 5. 5 < 7. dp[3] = 2. Dãy: [..., 5, 7]. Lớn nhất kết thúc tại 5 là [2, 5]. Ghép 7 ta có [2, 5, 7].
- j = 4: arr[4] = 3. 3 < 7. dp[4] = 2. Dãy: [..., 3, 7]. Lớn nhất kết thúc tại 3 là [2, 3]. Ghép 7 ta có [2, 3, 7].
- Max dp[j] cho j < 5 và arr[j] < arr[5] là max(dp[2], dp[3], dp[4]) = max(1, 2, 2) = 2.
- dp[5] = 1 + max(dp[j]...) = 1 + 2 = 3.
dp[6] (cho arr[6] = 101):
- Xem xét tất cả j < 6 mà arr[j] < 101. Tất cả đều nhỏ hơn 101.
- Max dp[j] cho j = 0..5 là max(1, 1, 1, 2, 2, 3) = 3.
- dp[6] = 1 + 3 = 4. (Ví dụ dãy: [2, 3, 7, 101])
dp[7] (cho arr[7] = 18):
- Xem xét tất cả j < 7 mà arr[j] < 18.
- arr[0]=10 (dp[0]=1), arr[1]=9 (dp[1]=1), arr[2]=2 (dp[2]=1), arr[3]=5 (dp[3]=2), arr[4]=3 (dp[4]=2), arr[5]=7 (dp[5]=3). arr[6]=101 (không nhỏ hơn 18).
- Max dp[j] cho các j thỏa mãn là max(dp[0], dp[1], dp[2], dp[3], dp[4], dp[5]) = max(1, 1, 1, 2, 2, 3) = 3.
- dp[7] = 1 + 3 = 4. (Ví dụ dãy: [2, 3, 7, 18])

Mảng dp cuối cùng sẽ là [1, 1, 1, 2, 2, 3, 4, 4]. Giá trị lớn nhất trong mảng dp là 4. Vậy độ dài LIS là 4.

C++ Code cho Phương pháp O(N^2)

#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS_O_N_Squared(const std::vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    int n = nums.size();
    std::vector<int> dp(n, 1); // Khởi tạo mỗi dp[i] = 1 (LIS kết thúc tại i có ít nhất 1 phần tử là chính nó)

    int max_lis_length = 1; // Độ dài LIS tối thiểu là 1 (nếu dãy không rỗng)

    // Duyệt qua từng phần tử của dãy
    for (int i = 1; i < n; ++i) {
        // Với mỗi phần tử nums[i], duyệt qua TẤT CẢ các phần tử đứng trước nó
        for (int j = 0; j < i; ++j) {
            // Nếu nums[j] nhỏ hơn nums[i]
            if (nums[j] < nums[i]) {
                // Có thể mở rộng LIS kết thúc tại j bằng cách thêm nums[i] vào
                // Cập nhật dp[i] nếu tìm thấy dãy con tăng dài hơn
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        // Sau khi xem xét tất cả các j < i, dp[i] đã chứa độ dài LIS kết thúc tại i
        // Cập nhật độ dài LIS tổng thể nếu dp[i] lớn hơn max_lis_length hiện tại
        max_lis_length = std::max(max_lis_length, dp[i]);
    }

    return max_lis_length;
}

int main() {
    std::vector<int> arr1 = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "LIS length for [10, 9, 2, 5, 3, 7, 101, 18] (O(N^2)): "
              << lengthOfLIS_O_N_Squared(arr1) << std::endl; // Output: 4

    std::vector<int> arr2 = {0, 1, 0, 3, 2, 3};
    std::cout << "LIS length for [0, 1, 0, 3, 2, 3] (O(N^2)): "
              << lengthOfLIS_O_N_Squared(arr2) << std::endl; // Output: 4 ([0, 1, 2, 3] hoặc [0, 1, 3])

    std::vector<int> arr3 = {7, 7, 7, 7, 7, 7, 7};
    std::cout << "LIS length for [7, 7, 7, 7, 7, 7, 7] (O(N^2)): "
              << lengthOfLIS_O_N_Squared(arr3) << std::endl; // Output: 1 ([7])

    std::vector<int> arr4 = {1, 2, 3, 4, 5};
    std::cout << "LIS length for [1, 2, 3, 4, 5] (O(N^2)): "
              << lengthOfLIS_O_N_Squared(arr4) << std::endl; // Output: 5

    std::vector<int> arr5 = {5, 4, 3, 2, 1};
     std::cout << "LIS length for [5, 4, 3, 2, 1] (O(N^2)): "
              << lengthOfLIS_O_N_Squared(arr5) << std::endl; // Output: 1

    return 0;
}

Giải thích Code O(N^2)

Hàm lengthOfLIS_O_N_Squared nhận một vector nums làm đầu vào.
Chúng ta xử lý trường hợp dãy rỗng.
Khởi tạo vector dp cùng kích thước với nums, tất cả giá trị ban đầu đều là 1. Điều này là đúng vì mỗi phần tử riêng lẻ tạo thành một dãy con tăng có độ dài 1.
Biến max_lis_length dùng để theo dõi độ dài LIS dài nhất tìm được cho đến hiện tại. Ban đầu nó là 1.
Vòng lặp ngoài chạy từ i = 1 đến n-1. Vòng lặp này xem xét từng phần tử nums[i] để tính dp[i].
Vòng lặp trong chạy từ j = 0 đến i-1. Vòng lặp này duyệt qua tất cả các phần tử nums[j] đứng trước nums[i].
Bên trong vòng lặp trong, chúng ta kiểm tra điều kiện nums[j] < nums[i]. Nếu điều kiện này đúng, có nghĩa là nums[i] có thể nối vào cuối một dãy con tăng kết thúc tại nums[j]. Độ dài của dãy mới này sẽ là dp[j] + 1.
Chúng ta cập nhật dp[i] bằng giá trị lớn nhất giữa dp[i] hiện tại và dp[j] + 1. Việc này đảm bảo rằng dp[i] luôn lưu trữ độ dài của dãy con tăng dài nhất kết thúc tại nums[i] mà có phần tử đứng ngay trước nums[i] là nums[j]. Bằng cách xét tất cả các j < i, dp[i] sẽ tìm được độ dài tối ưu dựa trên các phần tử đứng trước nó.
Sau khi vòng lặp trong kết thúc (đã xét tất cả j < i), dp[i] đã được tính chính xác. Chúng ta cập nhật max_lis_length nếu dp[i] lớn hơn giá trị hiện tại của max_lis_length.
Cuối cùng, hàm trả về max_lis_length.

Độ phức tạp thời gian của phương pháp này là O(N^2) vì có hai vòng lặp lồng nhau, mỗi vòng lặp chạy tới N lần. Độ phức tạp không gian là O(N) để lưu trữ mảng dp. Với N lên đến vài nghìn, O(N^2) có thể chậm. Chúng ta có thể làm tốt hơn.

Phương pháp 2: Tối ưu hóa bằng Quy hoạch động kết hợp Tìm kiếm nhị phân - Độ phức tạp O(N log N)

Đây là phương pháp hiệu quả hơn và thường được sử dụng trong các bài toán có giới hạn N lớn (ví dụ: N = 10^5). Ý tưởng ở đây phức tạp hơn một chút, nhưng mang lại cải thiện đáng kể về hiệu suất.

Thay vì lưu trữ độ dài LIS kết thúc tại mỗi vị trí i, chúng ta sẽ duy trì một mảng (hay vector) gọi là tail. Mảng tail này có một tính chất đặc biệt:

tail[k] sẽ lưu trữ giá trị nhỏ nhất mà một dãy con tăng có độ dài k+1 có thể kết thúc.

Chúng ta sẽ duyệt qua các phần tử của dãy đầu vào arr một lần. Khi xử lý phần tử arr[i]:

Nếu arr[i] lớn hơn phần tử cuối cùng của mảng tail, điều đó có nghĩa là chúng ta đã tìm thấy một phần tử có thể mở rộng dãy con tăng dài nhất hiện tại. Ta thêm arr[i] vào cuối mảng tail. Độ dài LIS tăng lên 1.
Nếu arr[i] không lớn hơn phần tử cuối cùng của mảng tail, điều đó có nghĩa là arr[i] không thể trực tiếp mở rộng LIS dài nhất hiện tại. Tuy nhiên, nó có thể giúp tạo ra một dãy con tăng có cùng độ dài với một dãy con tăng nào đó đã tìm thấy trước đó, nhưng kết thúc bằng một giá trị nhỏ hơn (arr[i] thay vì giá trị cũ). Việc thay thế này là quan trọng vì nó giữ cho mảng tail có các giá trị cuối nhỏ nhất có thể cho mỗi độ dài, từ đó tạo cơ hội cho các phần tử sau này mở rộng dãy con tăng.
- Trong trường hợp này, chúng ta cần tìm vị trí trong mảng tail mà arr[i] có thể thay thế. Vị trí đó chính là phần tử nhỏ nhất trong tail mà lớn hơn hoặc bằng arr[i]. Vì mảng tail luôn được giữ có thứ tự tăng dần (tại sao? Nếu tail[k] là giá trị nhỏ nhất kết thúc IS độ dài k+1 và tail[k+1] là giá trị nhỏ nhất kết thúc IS độ dài k+2, thì chắc chắn tail[k] < tail[k+1] vì một IS độ dài k+2 có thể được tạo ra bằng cách thêm một phần tử vào IS độ dài k+1. Phần tử được thêm vào phải lớn hơn phần tử cuối của IS độ dài k+1. Do đó, giá trị cuối nhỏ nhất của IS độ dài k+2 phải lớn hơn giá trị cuối nhỏ nhất của IS độ dài k+1), chúng ta có thể sử dụng tìm kiếm nhị phân để tìm vị trí này một cách hiệu quả (O(log N)). Sau khi tìm thấy vị trí, ta thay thế phần tử tại vị trí đó bằng arr[i].

Độ dài LIS chính là kích thước cuối cùng của mảng tail.

Lưu ý quan trọng: Mảng tail không phải là một dãy con tăng thực tế của dãy gốc, mà nó chỉ là một công cụ để theo dõi các giá trị kết thúc nhỏ nhất cho các LIS có độ dài khác nhau.

Hãy theo dõi ví dụ arr = [10, 9, 2, 5, 3, 7, 101, 18] với phương pháp O(N log N).

Khởi tạo: tail là rỗng. Độ dài LIS L = 0.

arr[0] = 10: tail rỗng. Thêm 10 vào tail. tail = [10], L = 1.
arr[1] = 9: 9 không lớn hơn phần tử cuối (10). Tìm kiếm nhị phân trong tail để tìm phần tử nhỏ nhất >= 9. Đó là 10 ở index 0. Thay thế 10 bằng 9. tail = [9], L = 1. (LIS độ dài 1 kết thúc bằng 9 là [9], nhỏ hơn [10] nên tốt hơn)
arr[2] = 2: 2 không lớn hơn phần tử cuối (9). Tìm kiếm nhị phân trong tail để tìm phần tử nhỏ nhất >= 2. Đó là 9 ở index 0. Thay thế 9 bằng 2. tail = [2], L = 1. (LIS độ dài 1 kết thúc bằng 2 là [2])
arr[3] = 5: 5 lớn hơn phần tử cuối (2). Thêm 5 vào tail. tail = [2, 5], L = 2. (LIS độ dài 2 kết thúc bằng 5 có thể là [2, 5])
arr[4] = 3: 3 không lớn hơn phần tử cuối (5). Tìm kiếm nhị phân trong tail để tìm phần tử nhỏ nhất >= 3. Đó là 5 ở index 1. Thay thế 5 bằng 3. tail = [2, 3], L = 2. (LIS độ dài 2 kết thúc bằng 3 có thể là [2, 3]. Dãy con tăng dài nhất kết thúc bằng giá trị nhỏ hơn tốt hơn)
arr[5] = 7: 7 lớn hơn phần tử cuối (3). Thêm 7 vào tail. tail = [2, 3, 7], L = 3. (LIS độ dài 3 kết thúc bằng 7 có thể là [2, 3, 7])
arr[6] = 101: 101 lớn hơn phần tử cuối (7). Thêm 101 vào tail. tail = [2, 3, 7, 101], L = 4. (LIS độ dài 4 kết thúc bằng 101 có thể là [2, 3, 7, 101])
arr[7] = 18: 18 không lớn hơn phần tử cuối (101). Tìm kiếm nhị phân trong tail để tìm phần tử nhỏ nhất >= 18. Đó là 101 ở index 3. Thay thế 101 bằng 18. tail = [2, 3, 7, 18], L = 4$. (LIS độ dài 4 kết thúc bằng 18 có thể là[2, 3, 7, 18]`. Vẫn giữ độ dài 4, nhưng kết thúc bằng giá trị nhỏ hơn.)

Kết thúc duyệt, kích thước của tail là 4. Vậy độ dài LIS là 4.

C++ Code cho Phương pháp O(N log N)

Trong C++, chúng ta có thể sử dụng std::vector cho mảng tail và std::lower_bound để thực hiện tìm kiếm nhị phân. std::lower_bound(first, last, val) trả về iterator trỏ đến phần tử đầu tiên trong phạm vi [first, last) mà không nhỏ hơn val.

#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS_O_N_Log_N(const std::vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    // tail[k] lưu trữ giá trị nhỏ nhất kết thúc một LIS có độ dài k+1
    std::vector<int> tail;

    // Duyệt qua từng phần tử trong dãy đầu vào
    for (int num : nums) {
        // Tìm kiếm vị trí của num trong mảng tail
        // lower_bound tìm phần tử đầu tiên >= num
        auto it = std::lower_bound(tail.begin(), tail.end(), num);

        // Case 1: num lớn hơn tất cả các phần tử trong tail
        // Điều này có nghĩa là num có thể mở rộng LIS dài nhất hiện tại
        if (it == tail.end()) {
            tail.push_back(num); // Thêm num vào cuối tail
        }
        // Case 2: num không lớn hơn tất cả các phần tử trong tail
        // Điều này có nghĩa là num có thể thay thế một phần tử trong tail
        // để tạo ra một LIS có cùng độ dài nhưng kết thúc bằng giá trị nhỏ hơn
        else {
            *it = num; // Thay thế phần tử tại vị trí it bằng num
        }
        // Kích thước của tail luôn là độ dài LIS tìm được cho đến hiện tại
    }

    // Độ dài LIS cuối cùng chính là kích thước của mảng tail
    return tail.size();
}

int main() {
    std::vector<int> arr1 = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "LIS length for [10, 9, 2, 5, 3, 7, 101, 18] (O(N log N)): "
              << lengthOfLIS_O_N_Log_N(arr1) << std::endl; // Output: 4

    std::vector<int> arr2 = {0, 1, 0, 3, 2, 3};
    std::cout << "LIS length for [0, 1, 0, 3, 2, 3] (O(N log N)): "
              << lengthOfLIS_O_N_Log_N(arr2) << std::endl; // Output: 4

    std::vector<int> arr3 = {7, 7, 7, 7, 7, 7, 7};
    std::cout << "LIS length for [7, 7, 7, 7, 7, 7, 7] (O(N log N)): "
              << lengthOfLIS_O_N_Log_N(arr3) << std::endl; // Output: 1

    std::vector<int> arr4 = {1, 2, 3, 4, 5};
    std::cout << "LIS length for [1, 2, 3, 4, 5] (O(N log N)): "
              << lengthOfLIS_O_N_Log_N(arr4) << std::endl; // Output: 5

     std::vector<int> arr5 = {5, 4, 3, 2, 1};
     std::cout << "LIS length for [5, 4, 3, 2, 1] (O(N log N)): "
              << lengthOfLIS_O_N_Log_N(arr5) << std::endl; // Output: 1

    std::vector<int> arr6 = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
     std::cout << "LIS length for [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] (O(N log N)): "
              << lengthOfLIS_O_N_Log_N(arr6) << std::endl; // Output: 6 ([0, 2, 6, 9, 11, 15] hoặc [0, 4, 6, 9, 11, 15] etc.)

    return 0;
}

Giải thích Code O(N log N)

Hàm lengthOfLIS_O_N_Log_N nhận một vector nums.
Khởi tạo một vector tail rỗng. Đây là vector sẽ lưu trữ các giá trị kết thúc nhỏ nhất cho các LIS có độ dài khác nhau.
Vòng lặp for (int num : nums) duyệt qua từng phần tử num trong dãy đầu vào.
Đối với mỗi num, chúng ta sử dụng std::lower_bound(tail.begin(), tail.end(), num) để tìm vị trí it. lower_bound tìm kiếm trong tail (đảm bảo tail luôn tăng dần) và trả về iterator trỏ đến phần tử đầu tiên không nhỏ hơn num.
- Nếu it == tail.end(), điều này có nghĩa là num lớn hơn tất cả các phần tử hiện có trong tail. Vì tail[k] là giá trị nhỏ nhất kết thúc LIS độ dài k+1, nếu num lớn hơn phần tử cuối cùng của tail (là giá trị kết thúc nhỏ nhất của LIS dài nhất hiện tại), thì num có thể mở rộng LIS dài nhất thêm 1 phần tử. Ta thêm num vào cuối tail bằng tail.push_back(num);.
- Nếu it không phải là tail.end(), điều này có nghĩa là chúng ta tìm thấy một phần tử *it trong tail mà *it >= num. Ta thay thế phần tử tại vị trí it bằng num (*it = num;). Việc này không làm tăng độ dài LIS tìm thấy cho đến nay (kích thước tail không đổi), nhưng nó giúp chúng ta có một dãy con tăng có cùng độ dài nhưng kết thúc bằng giá trị num nhỏ hơn. Điều này rất quan trọng vì nó có thể cho phép các phần tử trong tương lai (lớn hơn num) mở rộng LIS từ vị trí này, điều mà chúng không thể làm được nếu giá trị kết thúc vẫn là *it (lớn hơn). Vị trí it chính xác là vị trí mà một LIS kết thúc bằng num sẽ có cùng độ dài với LIS kết thúc bằng *it trước đó.
Sau khi duyệt qua tất cả các phần tử, kích thước cuối cùng của vector tail chính là độ dài của dãy con tăng dài nhất.

Độ phức tạp thời gian của phương pháp này là O(N log N) vì chúng ta duyệt qua N phần tử, và với mỗi phần tử, chúng ta thực hiện một phép tìm kiếm nhị phân trong tail có kích thước tối đa là N, mất O(log N). Độ phức tạp không gian là O(N) để lưu trữ vector tail.

Bài tập ví dụ:

Frog SPOJ.

Một con ếch có thể nhảy 1, 2, 3 bước để có thể lên đến một đỉnh cần đến. Hãy đếm số các cách con ếch có thể nhảy đến đỉnh.

Input Format

Số nguyên dương N mô tả số bước con ếch cần di chuyển để nhảy tới đỉnh.(1<=N<=40)Vì đáp án sẽ rất lớn nên bạn hãy mode với 1e9+7.

Constraints

Output Format

In ra kết quả của bài toán

Ví dụ:

Dữ liệu vào

Dữ liệu ra

Chào bạn,

Đây là một bài toán điển hình có thể giải bằng Quy hoạch động (Dynamic Programming) hoặc đệ quy có nhớ (Memoization).

Hướng dẫn giải ngắn gọn:

Xác định trạng thái: Gọi dp[i] là số cách để con ếch nhảy đến được bước thứ i. Mục tiêu của chúng ta là tìm dp[N].
Tìm công thức truy hồi: Để đến được bước thứ i, con ếch có thể nhảy từ các bước trước đó bằng một trong ba cách:
- Nhảy 1 bước từ bước i-1.
- Nhảy 2 bước từ bước i-2.
- Nhảy 3 bước từ bước i-3.
Vì vậy, số cách để đến bước i chính là tổng số cách để đến bước i-1, i-2, và i-3. Công thức truy hồi là: dp[i] = dp[i-1] + dp[i-2] + dp[i-3] (áp dụng khi i >= 3).
Xác định các trường hợp cơ sở (Base Cases):
- dp[0]: Số cách để ở tại bước 0 (vị trí bắt đầu). Có 1 cách (không làm gì cả). dp[0] = 1.
- dp[1]: Số cách để đến bước 1. Chỉ có 1 cách: nhảy 1 bước từ 0. dp[1] = 1.
- dp[2]: Số cách để đến bước 2. Có 2 cách: nhảy (1, 1) hoặc nhảy (2). dp[2] = 2.
Xây dựng lời giải:
- Sử dụng một mảng (hoặc vector) dp có kích thước N+1 để lưu trữ kết quả cho từng bước.
- Khởi tạo các trường hợp cơ sở: dp[0], dp[1], dp[2] (lưu ý xử lý các trường hợp N=1, N=2 sao cho mảng không bị truy cập ngoài phạm vi).
- Lặp từ i = 3 đến N, tính giá trị dp[i] dựa trên công thức truy hồi: dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD, trong đó MOD = 1e9 + 7. Cần thực hiện phép modulo sau mỗi lần cộng để tránh tràn số.
Kết quả: Kết quả cuối cùng là dp[N].

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.