Khóa học CTDL và GT

Bài 29.5. Bài tập tổng hợp về tối ưu quy hoạch động

Chào mừng trở lại với series về Cấu trúc dữ liệu và Giải thuật!

Chúng ta đã cùng nhau khám phá sức mạnh của Quy hoạch động (Dynamic Programming - DP) - một kỹ thuật giải quyết vấn đề mạnh mẽ bằng cách chia nhỏ bài toán thành các bài toán con gối nhau và lưu trữ kết quả để tránh tính toán lặp lại. Tuy nhiên, đôi khi, giải pháp DP "cơ bản" của chúng ta có thể gặp phải những hạn chế về thời gian thực thi hoặc không gian bộ nhớ, đặc biệt với dữ liệu đầu vào lớn.

Đây chính là lúc các kỹ thuật tối ưu Quy hoạch động phát huy tác dụng! Tối ưu không chỉ giúp giải quyết những bài toán lớn hơn mà còn thể hiện sự hiểu biết sâu sắc về cấu trúc của bài toán và cách DP hoạt động. Trong bài viết này, chúng ta sẽ tập trung vào các kỹ thuật tối ưu phổ biến, đặc biệt là tối ưu không gian, thông qua việc luyện tập các bài toán điển hình với code minh họa bằng C++.

Hãy cùng đi sâu vào thế giới của những bài tập DP đòi hỏi sự khéo léo để tối ưu!

Vì sao cần tối ưu Quy hoạch động?

Mặc dù DP đã giúp chúng ta giảm độ phức tạp từ cấp số mũ (thường là từ brute force) xuống cấp đa thức, nhưng đôi khi độ phức tạp đa thức đó vẫn quá lớn.

• Tối ưu Thời gian: Một số bài toán DP có thể có độ phức tạp thời gian là $O(N^2)$, $O(N^3)$ hoặc thậm chí cao hơn do việc tính toán các trạng thái phụ thuộc vào nhiều trạng thái trước đó. Các kỹ thuật như sử dụng cấu trúc dữ liệu (như Segment Tree, Fenwick Tree), Convex Hull Trick, hay Monotonic Queue có thể giúp giảm thời gian tính toán chuyển trạng thái xuống còn $O(\log N)$ hoặc $O(1)$ trên mỗi trạng thái, từ đó giảm tổng độ phức tạp thời gian.
• Tối ưu Không gian: Bảng DP thường có kích thước lớn, đôi khi lên tới $O(N^2)$ hoặc $O(N \times W)$ (với $N$ là số lượng phần tử, $W$ là dung lượng/tổng). Khi $N$ hoặc $W$ rất lớn, bảng DP có thể vượt quá giới hạn bộ nhớ cho phép. May mắn thay, trong nhiều trường hợp, để tính toán trạng thái hiện tại, chúng ta chỉ cần một số lượng hạn chế các trạng thái trước đó (ví dụ: chỉ cần trạng thái ở bước trước đó hoặc hai bước trước đó). Điều này cho phép chúng ta thu nhỏ kích thước bảng DP từ $O(N \times \dots)$ xuống còn $O(\dots)$, nơi kích thước mới độc lập với $N$ (số bước/phần tử) và chỉ phụ thuộc vào các yếu tố khác của trạng thái.

Trong bài viết này, chúng ta sẽ tập trung chủ yếu vào kỹ thuật tối ưu không gian, vì nó là một trong những kỹ thuật phổ biến và tương đối dễ tiếp cận nhất khi bắt đầu làm quen với tối ưu DP.

Kỹ thuật Tối ưu Không gian

Ý tưởng chính của tối ưu không gian là nhận ra rằng để tính dp[i] hoặc dp[i][j], chúng ta chỉ cần các giá trị dp từ một "lớp" hoặc một số "lớp" ngay trước đó. Chúng ta không cần lưu trữ toàn bộ lịch sử các giá trị dp.

Thay vì dùng một mảng DP lớn dp[N][M], chúng ta có thể giảm xuống còn dp[2][M] (chỉ lưu hàng hiện tại và hàng trước đó) hoặc thậm chí dp[M] (chỉ lưu hàng hiện tại và sử dụng giá trị trước khi cập nhật làm giá trị của hàng trước đó).

Hãy minh họa điều này qua các ví dụ cụ thể!

Ví dụ 1: Bài toán "House Robber" (Cướp nhà)

Bài toán: Cho một danh sách các số nguyên dương nums biểu thị số tiền trong mỗi ngôi nhà trên một con phố. Một tên trộm muốn cướp nhiều tiền nhất có thể, với một ràng buộc duy nhất: hắn không thể cướp hai ngôi nhà kề nhau (nếu cướp nhà i, không thể cướp nhà i-1 và i+1). Hãy tìm số tiền tối đa mà tên trộm có thể cướp.

Ví dụ: nums = [1, 2, 3, 1]. Kết quả tối đa là 1 + 3 = 4 (cướp nhà 1 và nhà 3).

Phân tích DP cơ bản:

• Gọi dp[i] là số tiền tối đa có thể cướp được từ i+1 ngôi nhà đầu tiên (tức là từ nhà 0 đến nhà i).
• Để tính dp[i], tên trộm có hai lựa chọn đối với ngôi nhà thứ i:
  1. Không cướp nhà i: Số tiền tối đa vẫn là số tiền cướp được từ i ngôi nhà đầu tiên, tức là dp[i-1].
  2. Cướp nhà i: Để cướp nhà i (với số tiền nums[i]), tên trộm không được cướp nhà i-1. Vì vậy, tổng số tiền sẽ là số tiền cướp được từ i-1 ngôi nhà đầu tiên (đến nhà i-2) cộng với số tiền nums[i]. Số tiền cướp được từ i-1 ngôi nhà đầu tiên mà không cướp nhà i-1 chính là dp[i-2]. Vậy, số tiền trong trường hợp này là dp[i-2] + nums[i].
• dp[i] sẽ là giá trị lớn nhất trong hai lựa chọn này: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
• Base cases:
  • dp[0] = nums[0] (Chỉ có một nhà, cướp nó).
  • dp[1] = max(nums[0], nums[1]) (Có hai nhà, cướp nhà có nhiều tiền hơn). Hoặc cẩn thận hơn: dp[1] = số tiền tối đa từ 2 nhà đầu tiên. Có thể cướp nhà 0 (tiền nums[0]) hoặc nhà 1 (tiền nums[1]). Kết quả là max(nums[0], nums[1]).
• Kết quả cuối cùng là dp[n-1] (với n là số lượng nhà).

Code C++ DP cơ bản:

#include <vector>
#include <algorithm>

int rob_basic(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    std::vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = std::max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        dp[i] = std::max(dp[i-1], dp[i-2] + nums[i]);
    }

    return dp[n-1];
}

Độ phức tạp:

• Thời gian: $O(N)$, duyệt qua mảng nums một lần.
• Không gian: $O(N)$ để lưu trữ mảng dp.

Tối ưu Không gian:

Nhìn vào công thức dp[i] = max(dp[i-1], dp[i-2] + nums[i]), chúng ta thấy rằng để tính dp[i], chúng ta chỉ cần giá trị của dp[i-1] và dp[i-2]. Chúng ta không cần toàn bộ mảng dp từ dp[0] đến dp[i-3].

Điều này gợi ý rằng chúng ta chỉ cần lưu trữ hai giá trị trước đó. Chúng ta có thể sử dụng hai biến thay vì cả một mảng.

• Gọi prev2 là dp[i-2]
• Gọi prev1 là dp[i-1]
• Gọi current là dp[i]

Khi chúng ta tính current = max(prev1, prev2 + nums[i]), sau đó để chuẩn bị cho lần lặp tiếp theo (i+1), chúng ta cần cập nhật:

• prev2 sẽ trở thành giá trị trước đó của prev1.
• prev1 sẽ trở thành giá trị current vừa tính.

Code C++ DP tối ưu không gian:

#include <vector>
#include <algorithm>

int rob_optimized(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    // prev2 represents dp[i-2]
    // prev1 represents dp[i-1]
    int prev2 = nums[0];
    int prev1 = std::max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        // current represents dp[i]
        int current = std::max(prev1, prev2 + nums[i]);

        // Update for the next iteration
        prev2 = prev1;
        prev1 = current;
    }

    return prev1; // The final result is dp[n-1], which is stored in prev1
}

Giải thích code tối ưu:

1. Base cases: Xử lý các trường hợp n=0 và n=1 riêng biệt.
2. Initialization: Khởi tạo prev2 với giá trị tương ứng dp[0] và prev1 với giá trị dp[1] ban đầu.
3. Loop: Duyệt từ i = 2 đến n-1. Trong mỗi bước lặp:
   • Tính toán giá trị current (dp[i]) dựa trên prev1 (dp[i-1]) và prev2 (dp[i-2]).
   • Thực hiện cập nhật: Giá trị dp[i-1] cũ (lưu trong prev1) trở thành giá trị dp[i-2] mới cho bước lặp tiếp theo, nên gán prev2 = prev1. Giá trị dp[i] vừa tính (lưu trong current) trở thành giá trị dp[i-1] mới cho bước lặp tiếp theo, nên gán prev1 = current.
4. Return: Sau khi vòng lặp kết thúc, prev1 đang giữ giá trị của dp[n-1], là kết quả cuối cùng.

Độ phức tạp của giải pháp tối ưu:

• Thời gian: $O(N)$, vẫn duyệt qua mảng một lần.
• Không gian: $O(1)$, chỉ sử dụng vài biến hằng số.

Tuyệt vời! Chúng ta đã giảm không gian sử dụng từ tuyến tính xuống hằng số mà không ảnh hưởng đến thời gian thực thi.

Ví dụ 2: Bài toán "Unique Paths" (Đếm đường đi duy nhất)

Bài toán: Một robot đứng ở góc trên cùng bên trái của một lưới m x n. Robot chỉ có thể di chuyển xuống dưới hoặc sang phải. Robot muốn đi đến góc dưới cùng bên phải của lưới. Hỏi có bao nhiêu đường đi duy nhất có thể có?

Phân tích DP cơ bản:

• Gọi dp[i][j] là số đường đi duy nhất từ ô (0, 0) đến ô (i, j).
• Để đến ô (i, j), robot chỉ có thể đến từ ô ngay trên nó (i-1, j) hoặc ô ngay bên trái nó (i, j-1).
• Vì vậy, số đường đi đến (i, j) chính là tổng số đường đi đến (i-1, j) và số đường đi đến (i, j-1). Công thức: dp[i][j] = dp[i-1][j] + dp[i][j-1].
• Base cases:
  • Các ô ở hàng đầu tiên (i=0): Để đến ô (0, j) (với j > 0), chỉ có một cách duy nhất là đi thẳng từ (0, 0) sang phải liên tục. Vậy dp[0][j] = 1 cho tất cả j.
  • Các ô ở cột đầu tiên (j=0): Tương tự, để đến ô (i, 0) (với i > 0), chỉ có một cách duy nhất là đi thẳng từ (0, 0) xuống dưới liên tục. Vậy dp[i][0] = 1 cho tất cả i.
  • Ô (0, 0): Có 1 đường đi đến chính nó (đường đi rỗng). dp[0][0] = 1. (Các base cases trên đã bao gồm trường hợp này).
• Kết quả cuối cùng là dp[m-1][n-1].

Code C++ DP cơ bản:

#include <vector>

int uniquePaths_basic(int m, int n) {
    // dp[i][j] is the number of unique paths to reach (i, j)
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));

    // Base cases: first row and first column have only 1 path to each cell
    for (int i = 0; i < m; ++i) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; ++j) {
        dp[0][j] = 1;
    }

    // Fill the DP table
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

Độ phức tạp:

• Thời gian: $O(m \times n)$, duyệt qua toàn bộ lưới.
• Không gian: $O(m \times n)$ để lưu trữ bảng dp.

Tối ưu Không gian:

Để tính dp[i][j], chúng ta chỉ cần dp[i-1][j] (ô phía trên trong hàng trước) và dp[i][j-1] (ô bên trái trong cùng hàng).

Điều này có nghĩa là để tính hàng i, chúng ta chỉ cần dữ liệu từ hàng i-1. Chúng ta không cần lưu trữ các hàng 0 đến i-2.

Chúng ta có thể giảm bảng DP 2D dp[m][n] thành một bảng DP 1D có kích thước n. Bảng 1D này, gọi là dp_row, sẽ lưu trữ số đường đi đến các ô trong hàng hiện tại mà chúng ta đang tính.

• dp_row[j] sẽ biểu thị số đường đi đến ô (i, j).
• Công thức dp[i][j] = dp[i-1][j] + dp[i][j-1] trở thành dp_row[j] = dp_row_previous[j] + dp_row[j-1].
• Làm thế nào để có dp_row_previous[j]? Khi chúng ta đang tính toán hàng i, mảng dp_row hiện tại đang lưu trữ các giá trị của hàng i-1 (từ lần lặp trước). Vì vậy, dp_row_previous[j] chính là giá trị trước khi cập nhật của dp_row[j].

Cẩn thận khi cập nhật: Khi tính dp_row[j] dựa trên dp_row[j-1] và giá trị cũ của dp_row[j], chúng ta phải đảm bảo rằng dp_row[j-1] đã được cập nhật cho hàng hiện tại i, trong khi giá trị dp_row[j] chưa được cập nhật và vẫn là giá trị từ hàng i-1. Điều này gợi ý rằng chúng ta nên duyệt cột j từ trái sang phải (j tăng dần).

• Khi tính dp_row[j]:
  • dp_row[j-1] đã là giá trị của dp[i][j-1] (đã được cập nhật trong lần lặp j-1 của cùng hàng i).
  • Giá trị hiện tại của dp_row[j] vẫn là giá trị của dp[i-1][j] (từ hàng trước).
  • Vậy, dp_row[j] = current_dp_row[j] + updated_dp_row[j-1].

Code C++ DP tối ưu không gian:

#include <vector>

int uniquePaths_optimized(int m, int n) {
    // dp_row[j] will store the number of unique paths to reach (i, j)
    // where 'i' is the current row being processed.
    std::vector<int> dp_row(n, 1); // Initialize first row (or first column based on perspective)

    // Start from the second row (index 1) or second column depending on perspective
    // Here, we treat dp_row as representing the current row
    // Iterating through rows
    for (int i = 1; i < m; ++i) {
        // Iterating through columns
        // dp_row[j] = dp[i][j-1] + dp[i-1][j]
        // In optimized array: dp_row[j] = dp_row[j-1] (updated) + dp_row[j] (from previous row)
        for (int j = 1; j < n; ++j) {
            dp_row[j] = dp_row[j] + dp_row[j-1];
            // Explanation:
            // The old dp_row[j] was the number of paths to (i-1, j)
            // dp_row[j-1] has already been updated to the number of paths to (i, j-1)
            // So, new dp_row[j] = (paths to (i-1, j)) + (paths to (i, j-1))
        }
    }

    return dp_row[n-1]; // The final result is in the last cell of the last row
}

Giải thích code tối ưu:

1. Initialization: Mảng dp_row có kích thước n được khởi tạo với tất cả giá trị là 1. Điều này tương ứng với việc tất cả các ô ở hàng đầu tiên (index 0) có 1 đường đi duy nhất đến chúng. dp_row[j] ban đầu chính là dp[0][j] trong bảng 2D ban đầu.
2. Outer loop: Duyệt qua các hàng từ i = 1 đến m-1. Mỗi lần lặp của vòng ngoài là chúng ta đang tính toán số đường đi đến các ô trong hàng i.
3. Inner loop: Duyệt qua các cột từ j = 1 đến n-1. Đối với mỗi ô (i, j):
   • dp_row[j-1] đã được cập nhật trong lần lặp trước của vòng trong (với chỉ số j-1), nên nó đang lưu trữ số đường đi đến (i, j-1).
   • dp_row[j] (trước khi cập nhật) vẫn đang lưu trữ số đường đi đến (i-1, j) (giá trị từ vòng lặp ngoài trước đó).
   • Do đó, dp_row[j] mới (số đường đi đến (i, j)) bằng tổng của dp_row[j] cũ (dp[i-1][j]) và dp_row[j-1] mới (dp[i][j-1]).
4. Return: Sau khi duyệt hết các hàng, dp_row[n-1] sẽ chứa số đường đi đến ô (m-1, n-1).

Độ phức tạp của giải pháp tối ưu:

• Thời gian: $O(m \times n)$, vẫn duyệt qua toàn bộ lưới.
• Không gian: $O(n)$ để lưu trữ mảng 1D dp_row.

Chúng ta đã giảm không gian từ $O(m \times n)$ xuống $O(n)$. Nếu m rất lớn so với n, đây là một cải thiện đáng kể về bộ nhớ. (Hoặc nếu n rất lớn so với m, chúng ta có thể đảo ngược vai trò của m và n để tối ưu xuống $O(m)$).

Ví dụ 3: Bài toán "0/1 Knapsack" (Cái túi)

Bài toán: Cho n vật phẩm, mỗi vật có khối lượng weight[i] và giá trị value[i]. Cho một cái túi có sức chứa tối đa là W. Hãy chọn một tập hợp các vật phẩm sao cho tổng khối lượng của chúng không vượt quá W và tổng giá trị của chúng là lớn nhất. Mỗi vật chỉ có thể chọn một lần (0/1 Knapsack).

Phân tích DP cơ bản:

• Gọi dp[i][w] là giá trị tối đa có thể đạt được khi chỉ xét i vật phẩm đầu tiên (từ 1 đến i) với sức chứa túi là w.
• Để tính dp[i][w], chúng ta có hai lựa chọn với vật phẩm thứ i:
  1. Không chọn vật phẩm i: Giá trị tối đa vẫn là giá trị đạt được khi chỉ xét i-1 vật phẩm đầu tiên với sức chứa w, tức là dp[i-1][w].
  2. Chọn vật phẩm i: Chỉ có thể chọn nếu sức chứa hiện tại w đủ để chứa vật phẩm i (w >= weight[i]). Nếu chọn, giá trị đạt được là giá trị của vật phẩm i (value[i]) cộng với giá trị tối đa đạt được khi chỉ xét i-1 vật phẩm đầu tiên với sức chứa còn lại w - weight[i], tức là dp[i-1][w - weight[i]] + value[i].
• dp[i][w] sẽ là giá trị lớn nhất trong hai lựa chọn này:
  • Nếu w < weight[i]: dp[i][w] = dp[i-1][w] (Không thể chọn vật phẩm i).
  • Nếu w >= weight[i]: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]).
• Base cases:
  • dp[0][w] = 0 cho mọi w từ 0 đến W (Không có vật phẩm nào, giá trị = 0).
  • dp[i][0] = 0 cho mọi i từ 0 đến n (Sức chứa bằng 0, không thể bỏ vật nào vào, giá trị = 0).
• Kết quả cuối cùng là dp[n][W].

Code C++ DP cơ bản:

#include <vector>
#include <algorithm>

int knapsack_basic(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    // dp[i][w] = max value using first i items with max weight w
    // Using n+1 rows and W+1 columns for easier indexing (items 1 to n, weights 0 to W)
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    // Base cases are handled by initialization to 0

    for (int i = 1; i <= n; ++i) { // Iterate through items
        int current_weight = weights[i-1]; // weights/values are 0-indexed in input
        int current_value = values[i-1];

        for (int w = 0; w <= W; ++w) { // Iterate through capacities
            // Case 1: Don't include the current item
            dp[i][w] = dp[i-1][w];

            // Case 2: Include the current item if possible
            if (w >= current_weight) {
                dp[i][w] = std::max(dp[i][w], dp[i-1][w - current_weight] + current_value);
            }
        }
    }

    return dp[n][W];
}

Độ phức tạp:

• Thời gian: $O(N \times W)$, duyệt qua $N \times W$ trạng thái, mỗi trạng thái tính trong $O(1)$.
• Không gian: $O(N \times W)$ để lưu trữ bảng dp.

Khi N và W lớn (ví dụ $N=1000$, $W=100000$), bảng DP có thể lên tới $10^8$ phần tử, cần khoảng 400MB bộ nhớ (với int), có thể vượt quá giới hạn.

Tối ưu Không gian:

Tương tự bài Unique Paths, để tính hàng i (dp[i][w]), chúng ta chỉ cần dữ liệu từ hàng i-1 (dp[i-1][w] và dp[i-1][w - weight[i]]). Chúng ta có thể giảm bảng 2D dp[N+1][W+1] xuống còn một bảng 1D dp[W+1].

• Mảng 1D dp[w] sẽ lưu trữ giá trị tối đa đạt được với sức chứa w khi xét đến các vật phẩm đã qua.
• Khi xử lý vật phẩm thứ i, mảng dp đang lưu trữ kết quả khi xét i-1 vật phẩm. Chúng ta sẽ cập nhật mảng dp này để nó lưu trữ kết quả khi xét i vật phẩm.

Công thức dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) khi chuyển sang 1D sẽ là: dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

Vấn đề: Khi tính dp[w] cho vật phẩm thứ i, chúng ta cần giá trị dp[i-1][w] (chính là giá trị hiện tại của dp[w] trước khi cập nhật) và dp[i-1][w - weight[i]] (chính là giá trị hiện tại của dp[w - weight[i]] trước khi cập nhật).

Nếu chúng ta duyệt w từ trái sang phải (tăng dần), khi tính dp[w], giá trị dp[w - weight[i]] đã bị cập nhật dựa trên vật phẩm thứ i. Điều này làm hỏng công thức, vì chúng ta cần giá trị của dp[w - weight[i]] từ hàng trước (i-1), chứ không phải từ hàng hiện tại (i).

Giải pháp: Duyệt w từ phải sang trái (giảm dần), từ W về đến weight[i].

• Khi duyệt w giảm dần:
  • Tính dp[w] = max(dp[w], dp[w - weight[i]] + value[i]).
  • dp[w] (trước khi cập nhật) là dp[i-1][w].
  • dp[w - weight[i]] (khi duyệt w giảm dần, chỉ số w - weight[i] nhỏ hơn w, nên ô này chưa được cập nhật trong lần lặp hiện tại với vật phẩm i) chính là dp[i-1][w - weight[i]].
• Như vậy, duyệt w từ phải sang trái đảm bảo rằng khi cần dp[w - weight[i]], chúng ta lấy giá trị từ "hàng" trước đó (khi chưa xét vật phẩm i).

Code C++ DP tối ưu không gian:

#include <vector>
#include <algorithm>

int knapsack_optimized(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    // dp[w] will store the maximum value for capacity w, considering items processed so far.
    std::vector<int> dp(W + 1, 0);

    // Iterate through items
    for (int i = 0; i < n; ++i) {
        int current_weight = weights[i];
        int current_value = values[i];

        // Iterate through capacities from W down to current_weight
        // IMPORTANT: Iterate backwards to use values from the previous item's computation
        for (int w = W; w >= current_weight; --w) {
            // dp[w] = max( value without current item, value with current item )
            // value without current item is the existing dp[w]
            // value with current item is dp[w - current_weight] (from previous item's row) + current_value
            dp[w] = std::max(dp[w], dp[w - current_weight] + current_value);
        }
        // If w < current_weight, dp[w] remains unchanged (effectively dp[i][w] = dp[i-1][w])
    }

    return dp[W]; // The final result is the max value for capacity W after considering all items
}

Giải thích code tối ưu:

1. Initialization: Mảng dp có kích thước W + 1 được khởi tạo với tất cả giá trị là 0. dp[w] ban đầu biểu thị giá trị max với sức chứa w khi chưa xét vật phẩm nào.
2. Outer loop: Duyệt qua từng vật phẩm từ i = 0 đến n-1.
3. Inner loop: Duyệt sức chứa w từ W xuống đến weights[i]. Chỉ duyệt đến weights[i] vì với sức chứa nhỏ hơn, chúng ta không thể cho vật phẩm i vào túi.
4. Update: dp[w] = std::max(dp[w], dp[w - current_weight] + current_value);
   • dp[w] (trước dấu bằng) là giá trị tối đa với sức chứa w sau khi đã xét vật phẩm i.
   • dp[w] (sau dấu bằng) là giá trị tối đa với sức chứa w sau khi chỉ xét vật phẩm i-1 (hoặc các vật phẩm trước đó). Đây chính là dp[i-1][w] trong công thức 2D.
   • dp[w - current_weight] (sau dấu bằng) là giá trị tối đa với sức chứa w - weight[i] sau khi chỉ xét vật phẩm i-1. Đây chính là dp[i-1][w - weight[i]] trong công thức 2D, nhờ vào việc duyệt w từ phải sang trái.
   • Chúng ta lấy giá trị lớn nhất giữa việc không chọn vật phẩm i (giá trị cũ dp[w]) và chọn vật phẩm i (giá trị cũ dp[w - weight[i]] cộng với giá trị của vật phẩm i).
5. Return: Sau khi duyệt qua tất cả vật phẩm, dp[W] sẽ chứa giá trị tối đa cho túi có sức chứa W.

Độ phức tạp của giải pháp tối ưu:

• Thời gian: $O(N \times W)$, vẫn giữ nguyên.
• Không gian: $O(W)$ để lưu trữ mảng 1D dp.

Đây là một tối ưu không gian rất hiệu quả cho bài Knapsack khi W không quá lớn và là kỹ thuật kinh điển trong các bài toán DP trên mảng 1D hoặc 2D mà trạng thái chỉ phụ thuộc vào lớp trước đó.

Tóm lược các kỹ thuật tối ưu không gian

Qua các ví dụ trên, chúng ta thấy rằng tối ưu không gian trong DP thường dựa trên quan sát:

1. Xác định sự phụ thuộc: Trạng thái dp[i] hoặc dp[i][j] phụ thuộc vào những trạng thái nào của "lớp" trước đó (ví dụ: dp[i-1], dp[i-2], dp[i-1][j], dp[i][j-1], dp[i-1][w - weight[i]]).
2. Lưu trữ tối thiểu: Chỉ lưu trữ đủ các "lớp" trạng thái cần thiết để tính toán "lớp" hiện tại.
   • Nếu chỉ cần 1 lớp trước đó (ví dụ dp[i] chỉ cần dp[i-1]), có thể dùng 2 biến hoặc mảng kích thước 2 (rolling array).
   • Nếu cần 2 lớp trước đó (ví dụ dp[i] cần dp[i-1] và dp[i-2]), có thể dùng 3 biến hoặc mảng kích thước 3, hoặc đơn giản hơn là 2 biến cập nhật luân phiên như bài House Robber.
   • Nếu cần các trạng thái trong cùng một "lớp" nhưng từ bước trước đó (như bài Knapsack hoặc Unique Paths 2D -> 1D), có thể dùng mảng 1D và cần cẩn thận về thứ tự duyệt để đảm bảo sử dụng giá trị cũ trước khi chúng bị ghi đè.

Các kỹ thuật tối ưu khác (Giới thiệu)

Ngoài tối ưu không gian, còn có các kỹ thuật tối ưu thời gian phức tạp hơn:

• Sử dụng cấu trúc dữ liệu: Giảm thời gian chuyển trạng thái từ $O(N)$ xuống $O(\log N)$ hoặc $O(1)$ bằng cách dùng Segment Tree, Fenwick Tree, Sparse Table, v.v., để truy vấn hoặc cập nhật giá trị max/min/sum trên một khoảng.
• Convex Hull Trick: Áp dụng khi công thức chuyển trạng thái có dạng tối ưu hóa một hàm tuyến tính.
• Monotonic Queue (Dequeue): Tối ưu các bài toán DP dạng "sliding window minimum/maximum" hoặc khi cần tìm giá trị tối ưu trong một đoạn con kích thước cố định hoặc tăng/giảm dần.
• Divide and Conquer Optimization (Knuth Optimization): Áp dụng cho các bài toán DP trên khoảng/đoạn với một điều kiện nhất định về điểm chia tối ưu.
• State Compression: Sử dụng bitmask để biểu diễn tập con hoặc trạng thái mà các phương pháp thông thường không thể biểu diễn hiệu quả.

Những kỹ thuật này thường phức tạp hơn và đòi hỏi sự hiểu biết sâu sắc về cả DP lẫn cấu trúc dữ liệu và toán học. Chúng ta có thể khám phá chúng trong các bài tập nâng cao hơn sau này.

Bài tập ví dụ:

DSA04011

Cho 2 xâu nhị phân biểu diễn 2 số.Nhiệm vụ của bạn là đưa ra tích của 2 số đó.Ví dụ với xâu S1 = "1100" và S2 = "1010" ta sẽ có kết quả là 120.

Input Format

Cho 2 xâu s1 và s2 không quá 30 kí tự.

Constraints

.

Output Format

Đưa ra tích của 2 xâu nhị phân ấy.

Ví dụ:

Dữ liệu vào

01 01

Dữ liệu ra

1

Hướng dẫn giải bài này như sau:

1. Ý tưởng chính: Chuyển đổi hai xâu nhị phân thành các số nguyên dạng thập phân, sau đó nhân hai số nguyên này lại và in kết quả.
2. Kiểu dữ liệu: Vì tích của hai số có thể vượt quá phạm vi của kiểu int thông thường (với xâu dài đến 30 ký tự, giá trị có thể lên tới \(2^30, tích có thể lên tới \)2^60), bạn cần sử dụng kiểu dữ liệu long long để lưu trữ các số sau khi chuyển đổi và kết quả tích.
3. Chuyển đổi xâu nhị phân sang số nguyên: C++ cung cấp các cách hiệu quả để làm việc này. Bạn có thể tự viết hàm chuyển đổi bằng cách duyệt xâu từ phải sang trái và nhân với lũy thừa tăng dần của 2, hoặc sử dụng các hàm/lớp có sẵn. Một cách đơn giản là sử dụng hàm std::stoll (string to long long) với tham số cơ số (base) là 2. Ví dụ: std::stoll("1100", nullptr, 2) sẽ trả về 12 dưới dạng long long.
4. Các bước thực hiện:
   • Đọc hai xâu nhị phân đầu vào (ví dụ: s1, s2).
   • Sử dụng std::stoll(s1, nullptr, 2) để chuyển s1 thành một số long long (ví dụ: num1).
   • Sử dụng std::stoll(s2, nullptr, 2) để chuyển s2 thành một số long long (ví dụ: num2).
   • Tính tích của num1 và num2: long long result = num1 * num2;.
   • In giá trị của result ra màn hình.
5. Thư viện cần thiết: Đảm bảo include <iostream> cho nhập/xuất và <string> cho việc xử lý xâu và dùng std::stoll.

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