Bài 27.4: Tối ưu không gian trong bài toán Knapsack

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Sau khi đã tìm hiểu về cách giải bài toán Knapsack 0/1 bằng Quy hoạch động (Dynamic Programming - DP), chúng ta đã xây dựng được một bảng DP để lưu trữ kết quả trung gian. Cụ thể, chúng ta thường định nghĩa trạng thái dp[i][w] là giá trị lớn nhất có thể đạt được khi chỉ xem xét i vật phẩm đầu tiên với giới hạn trọng lượng là w.

Nhắc lại công thức truy hồi cơ bản:

dp[i][w] = dp[i-1][w] (Không chọn vật phẩm thứ i) Nếu weight[i] <= w: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) (So sánh giữa việc không chọn và có chọn vật phẩm thứ i)

Công thức này cho phép chúng ta điền vào bảng DP kích thước (n+1) x (W+1), với n là số lượng vật phẩm và W là trọng lượng tối đa của cái túi. Độ phức tạp về thời gian của giải pháp này là O(nW), điều này thường được chấp nhận.

Tuy nhiên, độ phức tạp về không gian (bộ nhớ) cũng là O(nW) do kích thước của bảng dp. Khi số lượng vật phẩm (n) hoặc trọng lượng tối đa (W) trở nên rất lớn, việc cấp phát bộ nhớ cho bảng dp có thể vượt quá giới hạn cho phép của hệ thống, dẫn đến lỗi bộ nhớ (memory error) hoặc chương trình chạy chậm do sử dụng quá nhiều bộ nhớ ảo (swap).

Đây chính là lúc chúng ta cần đến việc tối ưu không gian!

Quan sát lại công thức truy hồi: để tính giá trị dp[i][w], chúng ta chỉ cần các giá trị từ hàng i-1 (dp[i-1][...]). Điều này có nghĩa là, khi chúng ta đang tính toán cho hàng i, chúng ta không cần giữ toàn bộ các hàng từ 0 đến i-2 trong bộ nhớ nữa. Chúng ta chỉ cần hàng i-1.

Ý tưởng tối ưu không gian dựa trên nhận xét này là: thay vì lưu trữ toàn bộ bảng (n+1) x (W+1), chúng ta chỉ cần lưu trữ thông tin từ hàng trước đó để tính toán cho hàng hiện tại.

Có hai cách tiếp cận phổ biến để giảm không gian từ O(nW) xuống O(W):

Sử dụng hai hàng: Duy trì hai hàng trong bộ nhớ: một hàng đại diện cho trạng thái của dp[i-1] và một hàng để tính toán trạng thái dp[i].
Sử dụng một hàng duy nhất: Duy trì chỉ một hàng đại diện cho trạng thái hiện tại và cập nhật nó một cách cẩn thận để nó phản ánh trạng thái của hàng trước đó trong tính toán tiếp theo.

Hãy cùng đi sâu vào từng cách tiếp cận!

Cách 1: Tối ưu không gian với hai hàng (`O(W)` Space)

Như đã phân tích, để tính hàng i, chúng ta chỉ cần hàng i-1. Do đó, chúng ta có thể sử dụng một mảng 2 chiều có kích thước 2 x (W+1). Chúng ta sẽ sử dụng chỉ số hàng % 2 để luân phiên giữa hai hàng này.

Ví dụ:

Hàng 0 (tương ứng với dp[0]) sẽ được sử dụng để tính hàng 1 (tương ứng với dp[1]).
Hàng 1 sẽ được sử dụng để tính hàng 2. Tuy nhiên, thay vì dùng hàng 2, chúng ta sẽ dùng hàng 0 (vì 2 % 2 == 0).
Hàng i sẽ được tính dựa trên hàng (i-1) % 2 và kết quả sẽ được lưu vào hàng i % 2.

Chỉ số hàng hiện tại sẽ là current_row = i % 2, và chỉ số hàng trước đó sẽ là previous_row = (i - 1) % 2.

Công thức truy hồi sẽ trở thành: dp[current_row][w] = dp[previous_row][w] Nếu weight[i-1] <= w (lưu ý chỉ số mảng weight và value thường bắt đầu từ 0 hoặc 1 tùy cách cài đặt): dp[current_row][w] = max(dp[previous_row][w], dp[previous_row][w - weight[i-1]] + value[i-1])

(Lưu ý: trong code C++ minh họa dưới đây, tôi sẽ sử dụng chỉ số 0-based cho weight và value, nên vật phẩm thứ i sẽ có trọng lượng weight[i-1] và giá trị value[i-1]. Bảng DP sẽ có kích thước 2 x (W+1), và vật phẩm thứ i (với i chạy từ 1 đến n) sẽ được xem xét.)

Đây là cách cài đặt bằng C++:

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

int knapsack_optimized_two_rows(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    // Bảng DP kích thước 2 x (W+1)
    std::vector<std::vector<int>> dp(2, std::vector<int>(W + 1, 0));

    // Duyệt qua từng vật phẩm từ 1 đến n
    for (int i = 1; i <= n; ++i) {
        // Xác định chỉ số hàng hiện tại và hàng trước đó
        int current_row = i % 2;
        int previous_row = (i - 1) % 2;

        // Duyệt qua từng trọng lượng có thể từ 0 đến W
        for (int w = 0; w <= W; ++w) {
            // Mặc định không chọn vật phẩm thứ i
            dp[current_row][w] = dp[previous_row][w];

            // Nếu có thể chọn vật phẩm thứ i
            if (weights[i - 1] <= w) {
                // Tính giá trị nếu chọn vật phẩm thứ i
                int value_if_take = dp[previous_row][w - weights[i - 1]] + values[i - 1];

                // So sánh giá trị khi không chọn và khi chọn
                dp[current_row][w] = std::max(dp[current_row][w], value_if_take);
            }
        }
         // (Optional) Clear the previous row after using it for the current row
         // This is not strictly necessary for correctness with %2 but can be useful
         // in some variations or for clarity that the previous row is 'done'.
         // In this %2 approach, the previous_row will be overwritten when it becomes
         // the current_row for a future iteration.
         // std::fill(dp[previous_row].begin(), dp[previous_row].end(), 0);
    }

    // Kết quả cuối cùng nằm ở hàng cuối cùng được tính (hàng n % 2)
    return dp[n % 2][W];
}

int main() {
    int W = 10; // Trọng lượng tối đa của cái túi
    std::vector<int> weights = {2, 3, 4, 5}; // Trọng lượng của các vật phẩm
    std::vector<int> values = {3, 4, 5, 6};  // Giá trị tương ứng của các vật phẩm

    int maxValue = knapsack_optimized_two_rows(W, weights, values);
    std::cout << "Gia tri lon nhat (dung 2 hang): " << maxValue << std::endl; // Expected output: 10 (item 2 and 4, weights 3+5=8, value 4+6=10 OR item 1 and 4, weights 2+5=7, value 3+6=9 OR item 2 and 3, weights 3+4=7, value 4+5=9... wait, let's check. Items (2,3,4,5) and values (3,4,5,6) for W=10. Items (2,3), val 3+4=7, W=5. (2,4), val 3+5=8, W=6. (2,5), val 3+6=9, W=7. (3,4), val 4+5=9, W=7. (3,5), val 4+6=10, W=8. (4,5), val 5+6=11, W=9. (2,3,5), val 3+4+6=13, W=10. So max is 13. My manual calculation was wrong. The code should give 13)

    // Another example
    W = 7;
    weights = {1, 3, 4, 5};
    values = {1, 4, 5, 7};
    maxValue = knapsack_optimized_two_rows(W, weights, values);
    std::cout << "Gia tri lon nhat (dung 2 hang, VD2): " << maxValue << std::endl; // Expected output: 9 (item 3 and 4, weights 3+4=7, value 4+5=9 OR item 1 and 4+5? No. Items 1(1,1), 3(3,4), 4(4,5), 5(5,7). W=7. (3,4) -> W=3+4=7, V=4+5=9. (1,3,4) -> W=1+3+4=8 > 7. (1,3) W=4, V=5. (1,4) W=5, V=6. (1,5) W=6, V=8. (3,5) W=8 > 7. (4,5) W=9 > 7. Best is 9.)

    return 0;
}

Giải thích Code:

Chúng ta khai báo dp là vector<vector<int>> có kích thước 2 x (W+1).
Vòng lặp ngoài for (int i = 1; i <= n; ++i) duyệt qua từng vật phẩm từ vật phẩm thứ nhất đến thứ n.
Trong mỗi lần lặp, current_row = i % 2 và previous_row = (i - 1) % 2 xác định chỉ số hàng trong mảng dp 2x(W+1) mà chúng ta đang sử dụng để tính toán (hàng hiện tại) và hàng chứa dữ liệu từ bước trước đó (hàng trước).
Vòng lặp trong for (int w = 0; w <= W; ++w) duyệt qua tất cả các trọng lượng có thể từ 0 đến W.
dp[current_row][w] = dp[previous_row][w]; thực hiện trường hợp không chọn vật phẩm thứ i. Giá trị lớn nhất với trọng lượng w khi xem xét i vật phẩm (mà không chọn vật phẩm i) chính là giá trị lớn nhất với trọng lượng w khi xem xét i-1 vật phẩm.
if (weights[i - 1] <= w) kiểm tra xem có đủ chỗ trong cái túi để đặt vật phẩm thứ i hay không.
Nếu có đủ chỗ, chúng ta tính toán giá trị nếu chọn vật phẩm thứ i: dp[previous_row][w - weights[i - 1]] + values[i - 1]. Điều này có nghĩa là giá trị tối đa có được từ i-1 vật phẩm với trọng lượng còn lại sau khi đặt vật phẩm i (w - weights[i - 1]), cộng thêm giá trị của vật phẩm i.
dp[current_row][w] = std::max(dp[current_row][w], value_if_take); cập nhật giá trị tối đa cho trạng thái dp[i][w] bằng cách lấy giá trị lớn nhất giữa việc không chọn vật phẩm i và có chọn vật phẩm i.
Sau khi vòng lặp trong kết thúc cho một vật phẩm i, hàng dp[current_row] đã được điền đầy đủ các giá trị dp[i][w] cho mọi w. Ở bước tiếp theo (i+1), hàng này sẽ trở thành hàng previous_row và hàng còn lại sẽ trở thành current_row.
Kết quả cuối cùng là dp[n % 2][W], là giá trị lớn nhất khi xem xét tất cả n vật phẩm với trọng lượng tối đa W.

Cách tiếp cận này giảm không gian bộ nhớ xuống O(W) vì kích thước mảng dp chỉ phụ thuộc vào W (cụ thể là 2 * (W+1)). Tuy nhiên, chúng ta vẫn có thể làm tốt hơn nữa!

Cách 2: Tối ưu không gian với một hàng duy nhất (`O(W)` Space)

Phương pháp này là cách tối ưu không gian hiệu quả nhất cho bài toán Knapsack 0/1 DP, chỉ sử dụng một mảng 1 chiều có kích thước (W+1).

Ý tưởng là sử dụng một mảng dp duy nhất có kích thước W+1, trong đó dp[w] sẽ đại diện cho giá trị lớn nhất có thể đạt được với trọng lượng tối đa w khi xem xét các vật phẩm đã được xử lý đến thời điểm hiện tại.

Khi chúng ta xử lý vật phẩm thứ i, chúng ta muốn cập nhật mảng dp sao cho dp[w] mới (sau khi xem xét vật phẩm i) phản ánh: dp[w] mới = max(dp[w] cũ, dp[w - weight[i-1]] cũ + value[i-1])

Đây là điểm mấu chốt: dp[w] cũ chính là dp[i-1][w] từ công thức ban đầu, và dp[w - weight[i-1]] cũ chính là dp[i-1][w - weight[i-1]].

Nếu chúng ta duyệt trọng lượng w từ nhỏ đến lớn (ví dụ từ weight[i-1] đến W), khi chúng ta tính dp[w], chúng ta sẽ sử dụng giá trị dp[w - weight[i-1]]. Nhưng nếu w - weight[i-1] đã được cập nhật trong cùng một vòng lặp cho vật phẩm i (vì w - weight[i-1] < w), thì chúng ta sẽ vô tình sử dụng dp[i][w - weight[i-1]] thay vì dp[i-1][w - weight[i-1]]. Điều này tương đương với việc cho phép chọn vật phẩm thứ i nhiều lần (hoặc ít nhất là sử dụng kết quả đã bao gồm vật phẩm i để quyết định có chọn vật phẩm i nữa hay không), biến nó thành bài toán Unbounded Knapsack (Knapsack không giới hạn số lượng) hoặc gây ra kết quả sai cho bài toán 0/1.

Để ngăn chặn việc sử dụng giá trị dp đã được cập nhật bởi vật phẩm i trong cùng một lần lặp cho vật phẩm i, chúng ta phải duyệt trọng lượng w từ lớn đến nhỏ (từ W xuống đến weight[i-1]).

Khi duyệt w từ W xuống weight[i-1], giá trị dp[w - weight[i-1]] mà chúng ta cần để tính dp[w] luôn nằm ở chỉ mục nhỏ hơn w. Do chúng ta đang đi lùi, chỉ mục w - weight[i-1] chưa bị cập nhật bởi vật phẩm thứ i trong lần lặp hiện tại. Do đó, dp[w - weight[i-1]] lúc này vẫn là dp[i-1][w - weight[i-1]] theo đúng công thức truy hồi gốc!

Đây là kỹ thuật then chốt để tối ưu không gian xuống O(W) cho bài toán Knapsack 0/1 bằng DP.

Công thức cập nhật với một mảng 1 chiều: dp[w] = max(dp[w], dp[w - weight[i-1]] + value[i-1]) (Áp dụng khi w >= weight[i-1], duyệt w từ W xuống weight[i-1])

Dưới đây là code C++ cài đặt phương pháp này:

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

int knapsack_optimized_one_row(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    // Bảng DP kích thước 1 x (W+1)
    std::vector<int> dp(W + 1, 0);

    // Duyệt qua từng vật phẩm từ 1 đến n
    for (int i = 1; i <= n; ++i) {
        // Lấy trọng lượng và giá trị của vật phẩm thứ i (chỉ số 0-based trong vector)
        int current_weight = weights[i - 1];
        int current_value = values[i - 1];

        // Duyệt qua từng trọng lượng có thể TỪ LỚN ĐẾN NHỎ
        // Bắt đầu từ W xuống đến trọng lượng của vật phẩm hiện tại
        for (int w = W; w >= current_weight; --w) {
            // Công thức cập nhật:
            // dp[w] = max( giá trị khi KHÔNG chọn vật phẩm i, giá trị khi CÓ chọn vật phẩm i)
            // dp[w] (trước cập nhật) chính là giá trị tối đa với trọng lượng w khi xét i-1 vật phẩm
            // dp[w - current_weight] (trước cập nhật) chính là giá trị tối đa với trọng lượng w - weight[i-1] khi xét i-1 vật phẩm
            dp[w] = std::max(dp[w], dp[w - current_weight] + current_value);
        }
        // Sau khi vòng lặp trong kết thúc, mảng dp đã được cập nhật để phản ánh
        // kết quả khi xét i vật phẩm.
    }

    // Kết quả cuối cùng nằm ở dp[W]
    return dp[W];
}

int main() {
    int W = 10; // Trọng lượng tối đa của cái túi
    std::vector<int> weights = {2, 3, 4, 5}; // Trọng lượng của các vật phẩm
    std::vector<int> values = {3, 4, 5, 6};  // Giá trị tương ứng của các vật phẩm

    int maxValue = knapsack_optimized_one_row(W, weights, values);
    std::cout << "Gia tri lon nhat (dung 1 hang): " << maxValue << std::endl; // Expected output: 13

    // Another example
    W = 7;
    weights = {1, 3, 4, 5};
    values = {1, 4, 5, 7};
    maxValue = knapsack_optimized_one_row(W, weights, values);
    std::cout << "Gia tri lon nhat (dung 1 hang, VD2): " << maxValue << std::endl; // Expected output: 9

    return 0;
}

Giải thích Code:

Chúng ta khai báo dp là vector<int> có kích thước W+1. Ban đầu tất cả các phần tử đều là 0. dp[w] sẽ lưu trữ giá trị tối đa cho trọng lượng w.
Vòng lặp ngoài for (int i = 1; i <= n; ++i) duyệt qua từng vật phẩm.
Trong vòng lặp ngoài, chúng ta lấy current_weight và current_value của vật phẩm thứ i.
Vòng lặp trong for (int w = W; w >= current_weight; --w) là điểm khác biệt mấu chốt. Chúng ta duyệt trọng lượng w từ W giảm dần xuống đến current_weight (chúng ta chỉ cần xem xét các trọng lượng đủ lớn để có thể chứa vật phẩm hiện tại).
dp[w] = std::max(dp[w], dp[w - current_weight] + current_value); thực hiện việc cập nhật.
- dp[w] trước dòng này là giá trị tối đa cho trọng lượng w khi chỉ xét i-1 vật phẩm đầu tiên. Đây chính là dp[i-1][w] trong công thức gốc.
- dp[w - current_weight] trước dòng này là giá trị tối đa cho trọng lượng w - weight[i-1] khi chỉ xét i-1 vật phẩm đầu tiên. Đây chính là dp[i-1][w - weight[i-1]] trong công thức gốc.
- dp[w - current_weight] + current_value là giá trị nếu chúng ta chọn vật phẩm thứ i.
- std::max chọn giá trị tốt nhất giữa việc không chọn vật phẩm i (dp[w] cũ) và có chọn vật phẩm i.
Vì chúng ta duyệt w từ lớn xuống nhỏ, khi tính dp[w], giá trị dp[w - current_weight] (với w - current_weight < w) vẫn là giá trị từ bước i-1, chưa bị ảnh hưởng bởi vật phẩm i. Điều này đảm bảo chúng ta tuân thủ đúng công thức truy hồi của bài toán 0/1 Knapsack.
Sau khi duyệt hết các vật phẩm, dp[W] sẽ chứa giá trị tối đa có thể đạt được với trọng lượng tối đa W khi xét tất cả n vật phẩm.

Cách tiếp cận này chỉ sử dụng một mảng 1 chiều kích thước W+1, đạt được độ phức tạp không gian O(W). Đây là phương pháp phổ biến nhất khi bộ nhớ là hạn chế quan trọng đối với bài toán Knapsack 0/1. Độ phức tạp thời gian vẫn giữ nguyên là O(nW).

So sánh và Lựa chọn

Cả hai phương pháp tối ưu không gian đều đạt được độ phức tạp O(W).

Hai hàng: Dễ hiểu và cài đặt hơn một chút vì nó gần với ý tưởng gốc của bảng 2 chiều. Tuy nhiên, vẫn sử dụng gấp đôi bộ nhớ so với phương pháp một hàng.
Một hàng duy nhất: Đạt được tối ưu không gian tốt nhất (O(W) là tối thiểu cần thiết để lưu trữ kết quả cho mọi trọng lượng đến W). Cần lưu ý kỹ thuật duyệt ngược w để đảm bảo tính đúng đắn của bài toán 0/1.

Trong thực tế, phương pháp sử dụng một hàng duy nhất với duyệt ngược là phương pháp được sử dụng phổ biến nhất khi cần tối ưu không gian cho Knapsack 0/1 bằng DP.

Bài tập ví dụ:

Dự án

Trong một buổi phỏng vấn tuyển cộng tác viên, FullHouse Dev đã đưa ra một bài toán thú vị về việc lựa chọn dự án. Họ muốn tìm cách tối ưu hóa lợi nhuận từ việc tham gia các dự án cộng đồng, đồng thời đảm bảo không có sự chồng chéo về thời gian.

Bài toán

Có \(n\) dự án có thể tham gia. Với mỗi dự án, bạn biết được ngày bắt đầu, ngày kết thúc và số tiền thưởng. Bạn chỉ có thể tham gia một dự án trong một ngày. Hãy tìm số tiền thưởng tối đa mà bạn có thể nhận được.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(n\): số lượng dự án.
\(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\), và \(p_i\): ngày bắt đầu, ngày kết thúc và tiền thưởng.

OUTPUT FORMAT:

In ra một số nguyên: số tiền thưởng tối đa có thể nhận được.

Ràng buộc:

\(1 \leq n \leq 2 \cdot 10^5\)
\(1 \leq a_i \leq b_i \leq 10^9\)
\(1 \leq p_i \leq 10^9\)

Ví dụ

INPUT

OUTPUT

Giải thích

Trong ví dụ này, cách tối ưu là chọn dự án thứ nhất (thưởng 4) và dự án thứ ba (thưởng 2), tổng cộng nhận được 7 đơn vị tiền thưởng. Đây là phương án cho lợi nhuận cao nhất mà không có sự chồng chéo về thời gian giữa các dự án. Tuyệt vời, đây là hướng dẫn giải bài toán "Dự án" bằng phương pháp Quy hoạch động (Dynamic Programming), phù hợp với ràng buộc và yêu cầu không cung cấp code hoàn chỉnh:

Nhận diện bài toán: Đây là một biến thể của bài toán xếp lịch có trọng số (Weighted Interval Scheduling). Mục tiêu là chọn một tập hợp các khoảng thời gian (dự án) không chồng chéo nhau sao cho tổng trọng số (lợi nhuận) là lớn nhất.
Chuẩn bị dữ liệu:
- Lưu trữ các dự án dưới dạng các bộ ba (thời gian bắt đầu, thời gian kết thúc, lợi nhuận).
- Quan trọng: Sắp xếp các dự án theo thời gian kết thúc tăng dần. Việc sắp xếp này giúp ích cho bước quy hoạch động sau này.
Xây dựng Quy hoạch động (DP):
- Định nghĩa trạng thái DP: Gọi dp[i] là lợi nhuận tối đa có thể nhận được khi chỉ xét đến các dự án từ 1 đến i (sau khi đã sắp xếp theo thời gian kết thúc).
- Cơ sở DP: dp[0] = 0 (không có dự án nào, lợi nhuận bằng 0).
- Công thức chuyển trạng thái dp[i]: Để tính dp[i], ta có 2 lựa chọn cho dự án thứ i:
  - Không chọn dự án i: Lợi nhuận tối đa trong trường hợp này là dp[i-1].
  - Chọn dự án i: Nếu chọn dự án i, ta không thể chọn bất kỳ dự án nào chồng chéo với nó. Vì các dự án đã được sắp xếp theo thời gian kết thúc, ta cần tìm dự án j (với j < i) cuối cùng mà thời gian kết thúc của j nhỏ hơn hoặc bằng thời gian bắt đầu của dự án i. Nếu tìm được dự án j như vậy, lợi nhuận khi chọn dự án i sẽ là lợi nhuận_của_dự_án_i + dp[j]. Nếu không tìm thấy dự án j nào không chồng chéo trước đó, lợi nhuận chỉ là lợi nhuận_của_dự_án_i.
- Tìm dự án j không chồng chéo: Do các dự án đã được sắp xếp theo thời gian kết thúc, ta có thể dùng tìm kiếm nhị phân (binary search) trên các dự án từ 1 đến i-1 để tìm dự án có thời gian kết thúc lớn nhất nhưng vẫn nhỏ hơn hoặc bằng thời gian bắt đầu của dự án i.
Kết quả:
- Sau khi tính toán hết các giá trị dp[i] từ i = 1 đến n, giá trị dp[n] chính là lợi nhuận tối đa có thể nhận được.

Tóm tắt các bước thực hiện trong code C++:

Đọc n.
Tạo một struct hoặc pair để lưu trữ (start, end, profit) cho mỗi dự án.
Đọc n dự án và lưu vào một mảng/vector.
Sắp xếp mảng/vector các dự án theo thời gian kết thúc tăng dần.
Khởi tạo mảng/vector dp có kích thước n+1, với dp[0] = 0.
Duyệt qua các dự án từ i = 1 đến n:
- Tính lợi nhuận khi không chọn dự án i: option1 = dp[i-1].
- Tìm dự án j cuối cùng (trước i) không chồng chéo với dự án i sử dụng tìm kiếm nhị phân trên thời gian kết thúc của các dự án 1 đến i-1.
- Tính lợi nhuận khi chọn dự án i: option2 = lợi nhuận_của_dự_án_i + (dp[j] nếu tìm thấy j, ngược lại là 0).
- dp[i] = max(option1, option2).
In ra dp[n].

Độ phức tạp:

Sắp xếp: O(N log N).
Tính DP: N lần lặp, mỗi lần lặp có tìm kiếm nhị phân O(log N). Tổng O(N log N).
Tổng độ phức tạp thời gian: O(N log N).
Độ phức tạp không gian: O(N) cho lưu trữ dự án và mảng DP.

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

Comments

There are no comments at the moment.