Khóa học CTDL và GT

Bài 27.5: Bài tập tổng hợp về các biến thể Knapsack

Chào mừng các bạn đã quay trở lại với hành trình chinh phục Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với bài toán Knapsack 0/1 kinh điển - bài toán đặt nền móng cho rất nhiều kỹ thuật Lập trình động (Dynamic Programming - DP), hôm nay chúng ta sẽ cùng nhau mở rộng kiến thức bằng cách khám phá những biến thể thú vị của nó.

Bài toán Knapsack, hay còn gọi là bài toán Cái Túi, mô tả tình huống đơn giản nhưng mạnh mẽ: làm sao để đóng gói các vật phẩm vào một chiếc túi có sức chứa giới hạn sao cho đạt được mục tiêu nào đó (thường là tối đa hóa giá trị). Sự đơn giản này làm cho Knapsack trở thành một mô hình tuyệt vời để giải quyết vô số vấn đề trong thực tế, từ tối ưu hóa tài nguyên, phân bổ ngân sách cho đến cắt vật liệu công nghiệp.

Hiểu sâu về Knapsack và các biến thể của nó không chỉ giúp bạn giải quyết trực tiếp các bài toán dạng này mà còn trang bị cho bạn tư duy Lập trình động mạnh mẽ để nhận diện và xử lý các vấn đề khác có cấu trúc tương tự. Hãy cùng đi sâu vào thế giới đa dạng của Knapsack!

1. Knapsack 0/1 - Nền Tảng Vững Chắc (Ôn Lại)

Trước khi khám phá các biến thể, chúng ta hãy nhanh chóng ôn lại bài toán gốc: Knapsack 0/1.

Bài toán: Cho N vật phẩm, mỗi vật phẩm i có trọng lượng w[i] và giá trị v[i]. Chúng ta có một chiếc túi có sức chứa tối đa là W. Nhiệm vụ là chọn một tập hợp các vật phẩm sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất. Với mỗi vật phẩm, chúng ta chỉ có hai lựa chọn: hoặc chọn (1), hoặc không chọn (0).

Kỹ thuật DP: Chúng ta xây dựng một bảng DP để lưu trữ kết quả của các bài toán con.

• Trạng thái DP: dp[i][j] là giá trị lớn nhất có thể đạt được khi chỉ xét đến i vật phẩm đầu tiên và túi có sức chứa j.
• Công thức truy hồi: Khi xét vật phẩm thứ i:
  • Nếu không chọn vật phẩm i: Giá trị lớn nhất vẫn là giá trị đạt được khi chỉ xét i-1 vật phẩm với sức chứa j, tức là dp[i-1][j].
  • Nếu chọn vật phẩm i (chỉ khi w[i] <= j): Giá trị lớn nhất là giá trị đạt được khi xét i-1 vật phẩm với sức chứa còn lại j - w[i] cộng thêm giá trị của vật phẩm i, tức là dp[i-1][j - w[i]] + v[i].
  • Vậy, dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) nếu w[i] <= j, ngược lại dp[i][j] = dp[i-1][j].

Tối ưu không gian O(W): Quan sát công thức truy hồi, để tính dp[i][j], ta chỉ cần các giá trị từ hàng i-1. Điều này cho phép chúng ta giảm không gian lưu trữ từ O(N*W) xuống O(W) bằng cách chỉ sử dụng một mảng 1D dp[j], đại diện cho giá trị lớn nhất với sức chứa j.

Khi cập nhật mảng dp 1D, điều quan trọng cần nhớ là vòng lặp cho sức chứa j phải đi từ W xuống w[i]. Điều này đảm bảo rằng khi tính dp[j], giá trị dp[j - w[i]] mà ta sử dụng vẫn là giá trị từ "bước trước" (tức là không bao gồm vật phẩm i hiện tại), mô phỏng việc chỉ sử dụng mỗi vật phẩm một lần.

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

int main() {
    // Ví dụ Knapsack 0/1
    std::vector<int> weights = {10, 20, 30}; // Trọng lượng vật phẩm
    std::vector<int> values = {60, 100, 120}; // Giá trị vật phẩm
    int capacity = 50; // Sức chứa tối đa của túi
    int n = weights.size(); // Số lượng vật phẩm

    // Mảng DP với kích thước (capacity + 1), khởi tạo 0
    // dp[j] sẽ lưu giá trị lớn nhất có thể đạt được với sức chứa j
    std::vector<int> dp(capacity + 1, 0);

    // Duyệt qua từng vật phẩm
    for (int i = 0; i < n; ++i) {
        // Duyệt qua sức chứa từ lớn nhất xuống đến trọng lượng của vật phẩm hiện tại
        // Điều này đảm bảo mỗi vật phẩm chỉ được xét "đến" một lần cho mỗi sức chứa j
        for (int j = capacity; j >= weights[i]; --j) {
            // Công thức truy hồi:
            // dp[j] hiện tại là giá trị tốt nhất khi KHÔNG chọn vật phẩm i
            // dp[j - weights[i]] + values[i] là giá trị khi CHỌN vật phẩm i
            // (Lưu ý: dp[j - weights[i]] vẫn là giá trị tốt nhất từ các vật phẩm 0..i-1
            // do vòng lặp j đang giảm dần)
            dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    // Giá trị lớn nhất đạt được với sức chứa capacity
    std::cout << "Knapsack 0/1 Max Value: " << dp[capacity] << std::endl; // Output: 220 (Chọn vật 20kg (100) và 30kg (120))

    return 0;
}

Giải thích code:

• Mảng dp có kích thước capacity + 1. dp[j] lưu trữ giá trị tối đa có thể đạt được với sức chứa chính xác (hoặc nhỏ hơn, nhưng trong trường hợp tối ưu này thì thường là chính xác) j, chỉ sử dụng các vật phẩm đã được xử lý cho đến bước hiện tại.
• Vòng lặp ngoài duyệt qua từng vật phẩm (i).
• Vòng lặp trong duyệt qua sức chứa (j) từ capacity xuống weights[i]. Việc duyệt ngược này là bí quyết của tối ưu không gian O(W) cho 0/1 Knapsack. Nó đảm bảo rằng khi bạn tính dp[j], giá trị dp[j - weights[i]] mà bạn lấy để cộng thêm values[i] vẫn là giá trị trước khi xem xét vật phẩm i cho sức chứa j này.
• dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]); so sánh hai trường hợp: không chọn vật phẩm i (giá trị vẫn là dp[j] trước khi cập nhật) và chọn vật phẩm i (giá trị là dp[j - weights[i]] cộng thêm giá trị của vật phẩm i).

2. Knapsack Không Giới Hạn (Unbounded Knapsack) - Sức Mạnh Của Sự Lặp Lại

Đây là biến thể đầu tiên và phổ biến của Knapsack 0/1.

Bài toán: Giống Knapsack 0/1, nhưng mỗi vật phẩm có thể được chọn nhiều lần (không giới hạn số lượng).

Điểm khác biệt chính: Vì mỗi vật phẩm có thể dùng nhiều lần, khi chúng ta quyết định chọn vật phẩm i, phần sức chứa còn lại j - w[i] vẫn có thể sử dụng lại chính vật phẩm i đó.

Kỹ thuật DP:

• Trạng thái DP: Tương tự, dùng mảng 1D dp[j] là giá trị lớn nhất có thể đạt được với sức chứa j.
• Công thức truy hồi: Khi xét vật phẩm thứ i cho sức chứa j:
  • Nếu chọn vật phẩm i: Giá trị là dp[j - w[i]] + v[i]. Nhưng khác với 0/1 Knapsack, dp[j - w[i]] ở đây có thể đã bao gồm vật phẩm i rồi! Điều này là hợp lệ vì ta có thể chọn vật phẩm i nhiều lần.
  • dp[j] = max(dp[j], dp[j - w[i]] + v[i]) nếu w[i] <= j.

Tối ưu không gian O(W): Vẫn sử dụng mảng 1D dp kích thước O(W). Tuy nhiên, vòng lặp cho sức chứa j bây giờ phải đi từ weights[i] lên đến capacity.

Tại sao lại ngược lại so với 0/1? Khi duyệt j tăng dần, khi ta tính dp[j], giá trị dp[j - weights[i]] mà ta tham chiếu đã có thể được cập nhật bằng cách sử dụng vật phẩm i (nếu j - weights[i] >= weights[i]). Điều này chính xác là hành vi ta muốn: cho phép vật phẩm i đóng góp vào dp[j - weights[i]] và sau đó lại được sử dụng một lần nữa để đạt được dp[j].

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

int main() {
    // Ví dụ Knapsack Không Giới Hạn
    std::vector<int> weights = {10, 20, 30}; // Trọng lượng vật phẩm
    std::vector<int> values = {60, 100, 120}; // Giá trị vật phẩm
    int capacity = 50; // Sức chứa tối đa của túi
    int n = weights.size(); // Số lượng vật phẩm

    // Mảng DP với kích thước (capacity + 1), khởi tạo 0
    // dp[j] sẽ lưu giá trị lớn nhất có thể đạt được với sức chứa j
    std::vector<int> dp(capacity + 1, 0);

    // Duyệt qua từng vật phẩm
    for (int i = 0; i < n; ++i) {
        // Duyệt qua sức chứa từ trọng lượng của vật phẩm hiện tại lên đến lớn nhất
        // Điều này đảm bảo mỗi vật phẩm CÓ THỂ được sử dụng nhiều lần cho một sức chứa j
        for (int j = weights[i]; j <= capacity; ++j) {
            // Công thức truy hồi:
            // dp[j] hiện tại là giá trị tốt nhất ĐẾN thời điểm này cho sức chứa j
            // dp[j - weights[i]] + values[i] là giá trị khi CHỌN vật phẩm i.
            // dp[j - weights[i]] ở đây CÓ THỂ đã bao gồm vật phẩm i (nếu j-weights[i] đủ lớn),
            // cho phép chọn vật phẩm i nhiều lần.
            dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    // Giá trị lớn nhất đạt được với sức chứa capacity
    std::cout << "Unbounded Knapsack Max Value: " << dp[capacity] << std::endl; // Output: 300 (Chọn 5 lần vật 10kg (60*5=300))

    return 0;
}

Giải thích code:

• Cấu trúc tương tự như 0/1 Knapsack với tối ưu không gian O(W).
• Điểm khác biệt duy nhất (nhưng quan trọng) nằm ở vòng lặp trong duyệt sức chứa j. Nó đi từ weights[i] lên đến capacity. Điều này tạo ra sự khác biệt cơ bản trong công thức truy hồi: dp[j - weights[i]] giờ đây có thể tham chiếu đến một giá trị đã được cập nhật bằng cách sử dụng vật phẩm i, cho phép vật phẩm i được sử dụng lại để đạt được sức chứa j.

3. Bài Toán Tổng Con (Subset Sum) - Tìm Kiếm Sự Kết Hợp

Bài toán Subset Sum không hẳn là một "Knapsack" theo nghĩa truyền thống (tối đa hóa giá trị), nhưng nó có cấu trúc DP rất giống với Knapsack 0/1 và thường được xem như một biến thể hoặc bài toán liên quan chặt chẽ.

Bài toán: Cho một tập hợp các số nguyên dương nums và một số nguyên dương target. Xác định xem có tồn tại một tập con (subset) của nums mà các phần tử trong tập con đó có tổng bằng target hay không.

Liên hệ với Knapsack 0/1:

• Tập hợp các số nums là các "vật phẩm".
• Giá trị (value) và trọng lượng (weight) của mỗi "vật phẩm" đều chính là giá trị của số đó (nums[i]).
• Sức chứa (capacity) của túi là target.
• Mục tiêu là xác định xem có thể đạt được tổng giá trị (cũng là tổng trọng lượng) chính xác bằng target hay không, sử dụng mỗi số tối đa một lần (vì là tập con).

Kỹ thuật DP:

• Trạng thái DP: Sử dụng mảng boolean 1D dp[j], có nghĩa là "có thể đạt được tổng j hay không?".
• Khởi tạo: dp[0] là true (tổng 0 luôn có thể đạt được bằng cách không chọn số nào). Các dp[j] khác (j > 0) ban đầu là false.
• Công thức truy hồi: Khi xét số num hiện tại: Với mỗi tổng j mà ta đang xem xét (từ target xuống num), nếu ta đã có thể đạt được tổng j - num (tức là dp[j - num] là true), thì ta có thể đạt được tổng j bằng cách thêm số num.
  • dp[j] = dp[j] || dp[j - num] nếu num <= j.

Tối ưu không gian O(Target): Sử dụng mảng boolean 1D dp kích thước O(Target). Giống như 0/1 Knapsack, vòng lặp cho tổng j phải đi từ target xuống num để đảm bảo mỗi số chỉ được sử dụng một lần cho mỗi tổng j.

#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate

int main() {
    // Ví dụ Subset Sum
    std::vector<int> nums = {3, 34, 4, 12, 5, 2}; // Tập hợp các số
    int target = 9; // Tổng cần đạt

    // Mảng DP boolean, kích thước (target + 1)
    // dp[j] = true nếu có thể tạo ra tổng j, false nếu ngược lại
    std::vector<bool> dp(target + 1, false);
    dp[0] = true; // Có thể tạo ra tổng 0 (bằng cách không chọn số nào)

    // Duyệt qua từng số trong tập nums
    for (int num : nums) {
        // Duyệt qua tổng j từ target xuống đến num
        // Giống 0/1 Knapsack, duyệt ngược để đảm bảo mỗi số chỉ dùng 1 lần cho mỗi tổng j
        for (int j = target; j >= num; --j) {
            // Nếu có thể tạo ra tổng j - num (dp[j - num] là true)
            // Thì ta có thể tạo ra tổng j bằng cách thêm số num vào tập con tạo ra j - num
            dp[j] = dp[j] || dp[j - num];
        }
    }

    // Kết quả là dp[target]
    if (dp[target]) {
        std::cout << "Subset Sum: Possible to achieve sum " << target << std::endl; // Output: Possible... (3 + 4 + 2 = 9 hoặc 5 + 4 = 9)
    } else {
        std::cout << "Subset Sum: Not possible to achieve sum " << target << std::endl;
    }

    // Ví dụ khác: target = 30
    target = 30;
    std::vector<bool> dp2(target + 1, false);
    dp2[0] = true;
     for (int num : nums) {
        for (int j = target; j >= num; --j) {
            dp2[j] = dp2[j] || dp2[j - num];
        }
    }
    if (dp2[target]) {
        std::cout << "Subset Sum: Possible to achieve sum " << target << std::endl; // Output: Not possible...
    } else {
        std::cout << "Subset Sum: Not possible to achieve sum " << target << std::endl;
    }


    return 0;
}

Giải thích code:

• Mảng boolean dp lưu trữ khả năng đạt được từng tổng từ 0 đến target.
• dp[0] được khởi tạo là true.
• Vòng lặp ngoài duyệt qua từng số trong nums.
• Vòng lặp trong duyệt j ngược từ target xuống num. Lệnh dp[j] = dp[j] || dp[j - num]; có nghĩa là: "Tổng j có thể đạt được nếu nó đã đạt được trước khi xét số num (dp[j] ban đầu) HOẶC nó có thể đạt được bằng cách lấy một tập con đạt tổng j - num và thêm số num vào (dp[j - num])." Vòng lặp ngược đảm bảo rằng khi ta dùng dp[j - num], nó phản ánh khả năng đạt tổng j - num chỉ bằng các số trước số num hiện tại.

Bài toán Subset Sum cũng có thể được biến thể thành bài toán đếm số lượng tập con có tổng bằng target, hoặc tìm một tập con cụ thể nếu có. Kỹ thuật DP vẫn tương tự, chỉ thay đổi ý nghĩa của dp[j] (là số lượng cách thay vì boolean).

4. Bài Toán Đổi Tiền (Coin Change) - Đếm Hoặc Tối Ưu Số Lượng

Bài toán Coin Change cũng là một "họ hàng" thân cận của Knapsack, đặc biệt là Unbounded Knapsack. Nó có hai biến thể chính: đếm số cách đổi tiền và tìm số đồng xu ít nhất để đổi tiền. Chúng ta sẽ xem xét biến thể tìm số đồng xu ít nhất, vì nó liên quan đến việc tối ưu (minimizing) tương tự như Knapsack tối ưu (maximizing).

Bài toán: Cho một tập hợp các mệnh giá đồng xu coins và một số tiền amount. Tìm số đồng xu ít nhất cần thiết để tạo ra tổng số tiền amount. Giả sử mỗi mệnh giá có sẵn không giới hạn số lượng. Nếu không thể tạo ra tổng amount, trả về -1 (hoặc một giá trị đặc biệt như vô cực).

Liên hệ với Unbounded Knapsack:

• Các mệnh giá đồng xu coins là các "vật phẩm".
• Trọng lượng (weight) của mỗi vật phẩm là mệnh giá đồng xu (coins[i]).
• Giá trị (value) của mỗi vật phẩm là 1 (vì ta muốn tối thiểu hóa số lượng đồng xu, tương đương với tối đa hóa một giá trị âm -1, hoặc đơn giản là đếm số vật phẩm).
• Sức chứa (capacity) của túi là amount.
• Mục tiêu là tìm số lượng "vật phẩm" (đồng xu) ít nhất để đạt được "sức chứa" (tổng tiền) chính xác bằng amount. Mỗi đồng xu có thể sử dụng nhiều lần.

Kỹ thuật DP:

• Trạng thái DP: Mảng 1D dp[j] là số đồng xu ít nhất cần thiết để tạo ra tổng tiền j.
• Khởi tạo: dp[0] = 0 (cần 0 đồng xu để tạo ra tổng 0). Tất cả các dp[j] khác (j > 0) được khởi tạo với một giá trị "vô cực" (một số rất lớn) để biểu thị rằng tổng đó ban đầu là không thể đạt được.
• Công thức truy hồi: Khi xét đồng xu coin hiện tại: Với mỗi tổng j từ coin lên đến amount, nếu tổng j - coin là có thể đạt được (tức là dp[j - coin] không phải vô cực), thì ta có thể đạt được tổng j bằng cách thêm đồng xu coin. Số đồng xu cần thiết sẽ là dp[j - coin] + 1. Ta muốn tìm số đồng xu ít nhất, nên ta lấy giá trị nhỏ nhất giữa dp[j] hiện tại và dp[j - coin] + 1.
  • dp[j] = min(dp[j], dp[j - coin] + 1) nếu coin <= j và dp[j - coin] không phải vô cực.

Tối ưu không gian O(Amount): Sử dụng mảng 1D dp kích thước O(Amount). Giống như Unbounded Knapsack, vòng lặp cho tổng j phải đi từ coin lên đến amount. Điều này cho phép sử dụng lại cùng một mệnh giá đồng xu nhiều lần để đạt được tổng j.

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

// Định nghĩa một giá trị vô cực lớn
const int INF = 1e9; // Sử dụng 1e9 hoặc std::numeric_limits<int>::max()

int main() {
    // Ví dụ Coin Change (Minimum Coins)
    std::vector<int> coins = {1, 2, 5}; // Các mệnh giá đồng xu
    int amount = 11; // Tổng tiền cần đổi

    // Mảng DP, kích thước (amount + 1)
    // dp[j] = số đồng xu ít nhất để tạo ra tổng j
    std::vector<int> dp(amount + 1, INF); // Khởi tạo với vô cực
    dp[0] = 0; // Cần 0 đồng xu để tạo ra tổng 0

    // Duyệt qua từng mệnh giá đồng xu
    for (int coin : coins) {
        // Duyệt qua tổng tiền j từ coin lên đến amount
        // Giống Unbounded Knapsack, duyệt xuôi để cho phép dùng đồng xu coin nhiều lần
        for (int j = coin; j <= amount; ++j) {
            // Nếu tổng j - coin là có thể đạt được (dp[j - coin] không phải vô cực)
            if (dp[j - coin] != INF) {
                // Thì ta có thể đạt tổng j bằng cách thêm đồng xu coin.
                // Số đồng xu mới cần là dp[j - coin] + 1.
                // Cập nhật dp[j] với giá trị nhỏ nhất.
                dp[j] = std::min(dp[j], dp[j - coin] + 1);
            }
        }
    }

    // Kết quả là dp[amount]. Nếu vẫn là vô cực, nghĩa là không thể đổi được.
    if (dp[amount] == INF) {
        std::cout << "Coin Change (Min Coins): Cannot make amount " << amount << std::endl;
    } else {
        std::cout << "Coin Change (Min Coins): Minimum coins for " << amount << " is " << dp[amount] << std::endl; // Output: 3 (5 + 5 + 1)
    }

    // Ví dụ khác: amount = 7
    amount = 7;
    std::vector<int> dp2(amount + 1, INF);
    dp2[0] = 0;
     for (int coin : coins) {
        for (int j = coin; j <= amount; ++j) {
             if (dp2[j - coin] != INF) {
                dp2[j] = std::min(dp2[j], dp2[j - coin] + 1);
            }
        }
    }

    if (dp2[amount] == INF) {
        std::cout << "Coin Change (Min Coins): Cannot make amount " << amount << std::endl;
    } else {
        std::cout << "Coin Change (Min Coins): Minimum coins for " << amount << " is " << dp2[amount] << std::endl; // Output: 2 (5 + 2)
    }


    return 0;
}

Giải thích code:

• Mảng dp lưu trữ số đồng xu ít nhất. Khởi tạo với INF (vô cực) trừ dp[0]=0.
• Vòng lặp ngoài duyệt qua từng mệnh giá đồng xu.
• Vòng lặp trong duyệt tổng tiền j tăng từ coin lên amount. Điều này cho phép chúng ta sử dụng đồng xu coin hiện tại để đóng góp vào dp[j - coin] (nếu j - coin đủ lớn để chứa một đồng xu coin khác), và sau đó lại dùng thêm một đồng xu coin để đạt đến j.
• dp[j] = std::min(dp[j], dp[j - coin] + 1); cập nhật số đồng xu ít nhất cho tổng j. Ta so sánh giá trị hiện tại của dp[j] với giá trị có được bằng cách lấy số đồng xu ít nhất cho tổng j - coin và thêm một đồng xu coin.
• Kiểm tra dp[j - coin] != INF trước khi cập nhật để tránh tràn số hoặc sử dụng kết quả từ tổng không thể đạt được.

Bài toán Coin Change cũng có biến thể đếm số cách đổi tiền. Trong trường hợp đó, công thức truy hồi sẽ là dp[j] = dp[j] + dp[j - coin], và mảng DP sẽ lưu trữ số cách (kiểu int hoặc long long). Vòng lặp duyệt tổng tiền j vẫn đi tăng dần để cho phép các tổ hợp sử dụng lại đồng xu.

Kết nối các biến thể

Như bạn thấy, mặc dù có tên gọi và ngữ cảnh khác nhau, các bài toán Knapsack 0/1, Knapsack Không Giới Hạn, Subset Sum, và Coin Change (biến thể tối thiểu hóa) đều chia sẻ một lõi chung dựa trên Lập trình động trên một chiều "sức chứa" hoặc "tổng".

Sự khác biệt chính trong cách triển khai DP 1D nằm ở hướng duyệt vòng lặp cho chiều "sức chứa/tổng":

• Duyệt ngược (từ lớn xuống bé): Dành cho các bài toán mà mỗi "vật phẩm/số" chỉ được sử dụng tối đa một lần (như 0/1 Knapsack, Subset Sum).
• Duyệt xuôi (từ bé lên lớn): Dành cho các bài toán mà mỗi "vật phẩm/đồng xu" có thể sử dụng không giới hạn số lần (như Unbounded Knapsack, Coin Change).

Bài tập ví dụ:

Nhảy cóc trên lưới

Trong một chuyến tham quan bảo tàng, FullHouse Dev được giới thiệu một trò chơi cổ đại thú vị. Đó là một trò chơi nhảy cóc trên một tấm lưới, nơi người chơi phải tìm ra tất cả các cách có thể để di chuyển từ điểm xuất phát đến đích.

Bài toán

Bạn được cho một lưới kích thước \(n \times m\), trong đó mỗi ô chứa giá trị 0 hoặc 1. Một ô bị chặn nếu giá trị của nó là 1. Khi đứng tại một ô, bạn có thể thực hiện các bước di chuyển sau:

• Di chuyển sang phải đến ô không bị chặn gần nhất
• Di chuyển xuống dưới đến ô không bị chặn gần nhất

Xuất phát từ ô \((1,1)\), hãy xác định số cách có thể để đến được ô \((n,m)\).

Do kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(10^9 + 7\).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) - số hàng và số cột của lưới.
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi độ dài \(m\) gồm các ký tự '0' và '1'.

OUTPUT FORMAT:

• In ra một số nguyên duy nhất là số cách để đi từ ô \((1,1)\) đến ô \((n,m)\) theo modulo \(10^9 + 7\).

Ràng buộc:

• \(1 \leq n, m \leq 1000\)
• Mỗi ô chỉ chứa ký tự '0' hoặc '1'

Ví dụ

INPUT

3 3
000
011
000

OUTPUT

3

Giải thích

Có 3 cách để đi từ ô (1,1) đến ô (3,3):

1. (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)
2. (1,1) -> (1,2) -> (3,2) -> (3,3)
3. (1,1) -> (1,2) -> (1,3) -> (3,3) Tuyệt vời, đây là một bài toán điển hình về Quy hoạch động (Dynamic Programming - DP) trên lưới. Điểm đặc biệt ở đây là luật di chuyển "nhảy cóc đến ô không bị chặn gần nhất" thay vì chỉ di chuyển sang ô kề cạnh.

Dưới đây là hướng giải ngắn gọn bằng C++:

1. Xác định trạng thái DP:

   • Gọi dp[r][c] là số cách để đi từ ô (1,1) (hoặc (0,0) nếu dùng chỉ mục 0) đến ô (r,c).

2. Trường hợp cơ sở:

   • dp[1][1] (hoặc dp[0][0]) = 1 nếu ô (1,1) không bị chặn ('0').
   • Nếu ô (1,1) bị chặn ('1'), thì không có cách nào để bắt đầu, kết quả là 0.

3. Công thức truy hồi:

   • Để tính dp[r][c], ta cần xem xét tất cả các ô (r_prev, c) với r_prev < r sao cho một bước nhảy xuống từ (r_prev, c) sẽ đến đúng (r,c).
   • Tương tự, xem xét tất cả các ô (r, c_prev) với c_prev < c sao cho một bước nhảy sang phải từ (r, c_prev) sẽ đến đúng (r,c).
   • dp[r][c] là tổng số cách đến tất cả các ô (r_prev, c) và (r, c_prev) như vậy (tất cả tính theo modulo 10^9 + 7).
   • Nếu ô (r,c) bị chặn ('1'), thì dp[r][c] = 0.

4. Cách xác định ô nhảy đến:

   • Từ ô (r_prev, c) (không bị chặn), bước nhảy xuống dưới sẽ đến ô (r', c) không bị chặn đầu tiên sao cho r' > r_prev.
   • Từ ô (r, c_prev) (không bị chặn), bước nhảy sang phải sẽ đến ô (r, c') không bị chặn đầu tiên sao cho c' > c_prev.
   • Để tính dp[r][c], ta cần tìm ngược lại: những ô (r_prev, c) nào mà (r,c) là ô không bị chặn đầu tiên dưới chúng? Những ô (r, c_prev) nào mà (r,c) là ô không bị chặn đầu tiên bên phải chúng?

5. Tối ưu tính toán công thức truy hồi:

   • Việc trực tiếp tìm tất cả các ô (r_prev, c) và (r, c_prev) như ở bước 3 cho mỗi ô (r,c) sẽ tốn thời gian.
   • Nhận xét: Nếu ô (r, c) không bị chặn, thì nó có thể là đích nhảy xuống của nhiều ô (r_prev, c) phía trên nó, và đích nhảy phải của nhiều ô (r, c_prev) bên trái nó.
   • Cụ thể: ô (r, c) là đích nhảy xuống từ (r_prev, c) nếu grid[r_prev][c] == '0' và tất cả các ô grid[r_prev+1][c], ..., grid[r-1][c] đều là '1'.
   • Ô (r, c) là đích nhảy phải từ (r, c_prev) nếu grid[r][c_prev] == '0' và tất cả các ô grid[r][c_prev+1], ..., grid[r][c-1] đều là '1'.
   • Công thức truy hồi có thể được tính bằng cách cộng dồn (cumulative sum). Khi tính dp[r][c]:
     • Tổng các cách đến (r,c) từ phía trên: là tổng của dp[k][c] cho các k < r thỏa mãn điều kiện nhảy xuống.
     • Tổng các cách đến (r,c) từ phía trái: là tổng của dp[r][k] cho các k < c thỏa mãn điều kiện nhảy phải.
   • Có thể duy trì hai tổng tích lũy khi duyệt qua lưới: một tổng cho các bước nhảy từ trên xuống (theo cột) và một tổng cho các bước nhảy từ trái sang (theo hàng).
   • Khi tính dp[r][c] (nếu grid[r][c] == '0'):
     • dp[r][c] nhận đóng góp từ những ô (k,c) phía trên (k<r) mà (r,c) là ô không bị chặn đầu tiên dưới chúng. Tổng này có thể được tính dựa vào tổng tích lũy các dp từ các ô phía trên trong cùng cột c mà đang chờ ô không bị chặn tiếp theo để nhảy xuống. Nếu ô grid[r-1][c] == '1', thì tổng chờ từ (r-1,c) trở lên vẫn tiếp tục chờ và nhảy đến (r,c). Nếu ô grid[r-1][c] == '0', thì chỉ có chính (r-1,c) (nếu thỏa điều kiện nhảy) đóng góp vào tổng chờ cho (r,c) và các ô dưới nữa.
     • Tương tự cho đóng góp từ những ô (r,k) phía trái (k<c).
   • Cần duy trì hai mảng phụ, ví dụ sum_v[r][c] và sum_h[r][c], để lưu trữ tổng số cách đến các ô ở trên/trái mà có thể nhảy đến (r,c).
     • sum_v[r][c] = tổng dp[k][c] cho các k < r sao cho grid[j][c] == '1' với mọi k < j < r.
     • sum_h[r][c] = tổng dp[r][k] cho các k < c sao cho grid[r][j] == '1' với mọi k < j < c.
     • Nếu grid[r][c] == '0', thì dp[r][c] = (sum_v[r][c] + sum_h[r][c]) % MOD.
   • Recurrence cho sum_v và sum_h:
     • Nếu grid[r][c] == '1': sum_v[r][c] = 0, sum_h[r][c] = 0.
     • Nếu grid[r][c] == '0':
       • sum_v[r][c] = (sum_v[r-1][c] nếu r>0 và grid[r-1][c] == '1') + (dp[r-1][c] nếu r>0 và grid[r-1][c] == '0'). Tổng này cần tính modulo.
       • sum_h[r][c] = (sum_h[r][c-1] nếu c>0 và grid[r][c-1] == '1') + (dp[r][c-1] nếu c>0 và grid[r][c-1] == '0'). Tổng này cần tính modulo.
   • Base case cho sum_v, sum_h: sum_v[0][c] = 0 cho mọi c, sum_h[r][0] = 0 cho mọi r.

6. Thứ tự tính DP:

   • Duyệt qua lưới từ (1,1) đến (n,m) (hoặc (0,0) đến (n-1, m-1)) theo thứ tự hàng rồi cột.
   • Khi tính dp[r][c], ta đã có sẵn các giá trị dp của các ô ở hàng r các cột c_prev < c và các ô ở cột c các hàng r_prev < r.

7. Modulo:

   • Thực hiện phép toán modulo 10^9 + 7 sau mỗi lần cộng để tránh tràn số.

Tóm lại, hướng giải:

• Sử dụng mảng DP dp[n][m].
• Sử dụng hai mảng phụ sum_v[n][m] và sum_h[n][m] để hỗ trợ tính tổng đóng góp từ các ô phía trên và bên trái.
• Khởi tạo dp[0][0] = 1 nếu grid[0][0] == '0', ngược lại là 0. Các mảng phụ khởi tạo 0.
• Duyệt qua lưới từ (0,0) đến (n-1,m-1):
  • Nếu ô (r,c) bị chặn ('1'): dp[r][c] = 0, sum_v[r][c] = 0, sum_h[r][c] = 0.
  • Nếu ô (r,c) không bị chặn ('0'):
    • Tính sum_v[r][c] dựa vào sum_v[r-1][c] và dp[r-1][c] (nếu r>0) theo công thức truy hồi đã nêu.
    • Tính sum_h[r][c] dựa vào sum_h[r][c-1] và dp[r][c-1] (nếu c>0) theo công thức truy hồi đã nêu.
    • dp[r][c] = (sum_v[r][c] + sum_h[r][c]) % MOD. (Lưu ý trường hợp (0,0) đã khởi tạo).
• Kết quả là dp[n-1][m-1].

Độ phức tạp thời gian: O(nm) do mỗi ô được xử lý một lần. Độ phức tạp không gian: O(nm) cho các mảng DP và phụ.

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