Khóa học CTDL và GT

Bài 26.1. Bài toán đổi tiền và quy hoạch động

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau "mổ xẻ" một bài toán kinh điển trong lập trình thi đấu và khoa học máy tính: Bài toán đổi tiền (Coin Change Problem). Đây không chỉ là một bài toán thực tế mà còn là một ví dụ tuyệt vời để hiểu về sức mạnh của Quy hoạch động (Dynamic Programming).

Hãy tưởng tượng bạn là một nhân viên thu ngân, và bạn cần trả lại một khoản tiền cho khách hàng bằng cách sử dụng ít đồng xu nhất có thể từ các mệnh giá bạn có sẵn. Hoặc, bạn muốn biết có bao nhiêu cách khác nhau để trả lại chính xác số tiền đó. Đó chính là những biến thể của bài toán đổi tiền!

Chúng ta sẽ bắt đầu với cách tiếp cận ngây thơ (và kém hiệu quả), sau đó dần dần khám phá cách Quy hoạch động giải quyết vấn đề này một cách "thần kỳ" như thế nào.

Bài toán đổi tiền: Phiên bản tìm số xu tối thiểu

Phiên bản phổ biến nhất của bài toán này là: Cho một tập hợp các mệnh giá đồng xu có sẵn (ví dụ: {1, 2, 5} đơn vị tiền tệ) và một tổng số tiền mục tiêu Amount. Tìm số lượng đồng xu ít nhất cần thiết để tạo thành tổng số tiền Amount. Giả sử bạn có không giới hạn số lượng đồng xu của mỗi mệnh giá. Nếu không thể tạo thành tổng số tiền Amount, hãy trả về một giá trị đặc biệt (thường là -1 hoặc một số rất lớn).

Cách tiếp cận Ngây thơ: Đệ quy (Recursion)

Làm thế nào để giải quyết bài toán này một cách trực giác? Để tìm số xu tối thiểu cho số tiền Amount, chúng ta có thể thử dùng một đồng xu bất kỳ c từ tập các mệnh giá. Nếu dùng đồng xu c, thì phần còn lại chúng ta cần đổi là Amount - c. Số xu tối thiểu cho Amount sẽ là 1 (cho đồng xu c vừa dùng) cộng với số xu tối thiểu cho Amount - c. Chúng ta thử tất cả các đồng xu có thể dùng và chọn kết quả nhỏ nhất.

Đây chính là ý tưởng của đệ quy!

Các trường hợp cơ bản (Base Cases):

• Nếu Amount == 0, ta cần 0 đồng xu. Đây là trường hợp thành công.
• Nếu Amount < 0, ta không thể tạo thành số tiền âm. Đây là trường hợp không hợp lệ.

Công thức đệ quy: minCoins(Amount) = min(minCoins(Amount - coin) + 1) với mọi coin trong tập mệnh giá sao cho Amount >= coin.

Hãy thử cài đặt bằng C++:

#include <iostream>
#include <vector>
#include <algorithm> // For std::min
#include <limits>    // For std::numeric_limits

// Hàm đệ quy ngây thơ để tìm số xu tối thiểu
int minCoinsRecursive(int amount, const std::vector<int>& coins) {
    // Trường hợp cơ bản: Amount là 0
    if (amount == 0) {
        return 0;
    }

    // Trường hợp cơ bản: Amount âm (không hợp lệ)
    if (amount < 0) {
        // Trả về một giá trị lớn để biểu thị không thể đạt được
        return std::numeric_limits<int>::max();
    }

    // Khởi tạo min_count với giá trị rất lớn
    int min_count = std::numeric_limits<int>::max();

    // Duyệt qua tất cả các mệnh giá đồng xu
    for (int coin : coins) {
        // Chỉ xét nếu đồng xu hiện tại nhỏ hơn hoặc bằng amount
        if (amount >= coin) {
            // Gọi đệ quy cho phần còn lại (amount - coin)
            int remaining_count = minCoinsRecursive(amount - coin, coins);

            // Nếu kết quả đệ quy không phải là giá trị lớn (có thể đạt được)
            if (remaining_count != std::numeric_limits<int>::max()) {
                // Cập nhật min_count
                min_count = std::min(min_count, remaining_count + 1);
            }
        }
    }

    // Trả về số xu tối thiểu tìm được
    return min_count;
}

// Hàm wrapper để xử lý kết quả cuối cùng
int coinChangeRecursive(int amount, const std::vector<int>& coins) {
    int result = minCoinsRecursive(amount, coins);
    // Nếu kết quả là giá trị lớn, tức là không thể đổi tiền
    if (result == std::numeric_limits<int>::max()) {
        return -1; // Hoặc báo hiệu không thể đổi được
    }
    return result;
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    std::cout << "So xu toi thieu de doi " << amount << " (de quy): " << coinChangeRecursive(amount, coins) << std::endl; // Expected: 3 (5+5+1)

    // Một ví dụ khác có thể cho thấy sự kém hiệu quả của đệ quy ngây thơ
    std::vector<int> coins2 = {1, 2, 5};
    int amount2 = 30;
    // std::cout << "So xu toi thieu de doi " << amount2 << " (de quy): " << coinChangeRecursive(amount2, coins2) << std::endl; // Có thể rất chậm với các amount lớn

    return 0;
}

Giải thích code đệ quy:

• Hàm minCoinsRecursive(amount, coins):
  • Kiểm tra amount == 0: Nếu tiền cần đổi là 0, cần 0 xu, trả về 0.
  • Kiểm tra amount < 0: Nếu tiền cần đổi âm, không thể thực hiện, trả về numeric_limits<int>::max() để đánh dấu là không hợp lệ.
  • Khởi tạo min_count rất lớn.
  • Duyệt qua từng coin trong tập coins.
  • Nếu amount >= coin, ta có thể sử dụng coin này. Ta gọi đệ quy để tìm số xu tối thiểu cho amount - coin.
  • Nếu kết quả đệ quy không phải là max (tức là amount - coin có thể đổi được), ta so sánh 1 + remaining_count (1 xu hiện tại + số xu cho phần còn lại) với min_count hiện tại và cập nhật min_count.
  • Cuối cùng, trả về min_count.
• Hàm coinChangeRecursive(amount, coins): Là hàm "bao" để gọi minCoinsRecursive và kiểm tra kết quả cuối cùng có phải là max hay không.

Vấn đề với đệ quy ngây thơ:

Hãy xem ví dụ với coins = {1, 2, 5} và amount = 5. minCoins(5) sẽ gọi:

• minCoins(5-1=4)
• minCoins(5-2=3)
• minCoins(5-5=0) -> trả về 0. min_count = min(max, 0+1) = 1.

Bây giờ xét minCoins(4):

• minCoins(4-1=3)
• minCoins(4-2=2)
• minCoins(4-5=-1) -> trả về max.

Xét minCoins(3) (được gọi từ minCoins(5) và minCoins(4)):

• minCoins(3-1=2)
• minCoins(3-2=1)
• minCoins(3-5=-2) -> trả về max.

Bạn thấy gì ở đây? Cùng một bài toán con như minCoins(3), minCoins(2), minCoins(1)... đang được tính đi tính lại nhiều lần. Đây chính là hiện tượng overlapping subproblems (các bài toán con gối chồng). Điều này khiến độ phức tạp thời gian tăng lên theo cấp số nhân, rất kém hiệu quả với Amount lớn.

Đây là lúc Quy hoạch động bước vào sân khấu!

Quy hoạch động (Dynamic Programming): Giải cứu!

Quy hoạch động là một kỹ thuật giải thuật mạnh mẽ, thường được sử dụng cho các bài toán có hai đặc điểm chính:

1. Optimal Substructure (Cấu trúc tối ưu con): Lời giải tối ưu của bài toán lớn có thể được xây dựng từ lời giải tối ưu của các bài toán con. Trong bài toán đổi tiền, số xu tối thiểu cho Amount thực sự phụ thuộc vào số xu tối thiểu cho các Amount - coin nhỏ hơn.
2. Overlapping Subproblems (Các bài toán con gối chồng): Như chúng ta đã thấy ở trên, các bài toán con giống nhau được giải đi giải lại nhiều lần trong cây đệ quy.

Quy hoạch động giải quyết vấn đề "tính đi tính lại" này bằng cách lưu trữ kết quả của các bài toán con đã được giải, để khi gặp lại, chúng ta chỉ cần tra cứu thay vì tính toán lại. Có hai cách chính để thực hiện điều này:

1. Top-Down (Đệ quy có nhớ - Memoization): Bắt đầu từ bài toán lớn nhất (số tiền mục tiêu) và dùng đệ quy. Khi tính toán kết quả cho một bài toán con, lưu trữ nó vào một bảng (thường là mảng hoặc map). Trước khi tính toán cho một bài toán con, kiểm tra xem kết quả đã có trong bảng chưa. Nếu có, dùng ngay. Nếu chưa, tính toán, lưu vào bảng rồi mới dùng.
2. Bottom-Up (Lặp có bảng - Tabulation): Bắt đầu từ các bài toán con đơn giản nhất (số tiền nhỏ nhất) và xây dựng dần lên đến bài toán lớn nhất. Sử dụng một bảng (mảng DP) để lưu trữ kết quả của các bài toán con.

Cách tiếp cận 1: Top-Down DP (Memoization)

Chúng ta sẽ sửa đổi hàm đệ quy trước đó bằng cách thêm một mảng (gọi là memo hoặc dp) để lưu trữ kết quả.

#include <iostream>
#include <vector>
#include <algorithm> // For std::min
#include <limits>    // For std::numeric_limits

// Hàm đệ quy có nhớ
int minCoinsMemo(int amount, const std::vector<int>& coins, std::vector<int>& memo) {
    // Trường hợp cơ bản: Amount là 0
    if (amount == 0) {
        return 0;
    }

    // Trường hợp cơ bản: Amount âm (không hợp lệ)
    if (amount < 0) {
        return std::numeric_limits<int>::max();
    }

    // Kiểm tra xem kết quả cho amount này đã được tính chưa
    if (memo[amount] != -1) {
        return memo[amount]; // Nếu rồi, trả về kết quả đã lưu
    }

    // Nếu chưa, tính toán như đệ quy ngây thơ
    int min_count = std::numeric_limits<int>::max();
    for (int coin : coins) {
        if (amount >= coin) {
            int remaining_count = minCoinsMemo(amount - coin, coins, memo);
            if (remaining_count != std::numeric_limits<int>::max()) {
                min_count = std::min(min_count, remaining_count + 1);
            }
        }
    }

    // Lưu trữ kết quả trước khi trả về
    memo[amount] = min_count;
    return min_count;
}

// Hàm wrapper cho Top-Down DP
int coinChangeMemo(int amount, const std::vector<int>& coins) {
    // Mảng memo để lưu trữ kết quả. Kích thước amount + 1.
    // Khởi tạo với -1 để đánh dấu là chưa tính
    std::vector<int> memo(amount + 1, -1);

    int result = minCoinsMemo(amount, coins, memo);

    // Kiểm tra kết quả cuối cùng
    if (result == std::numeric_limits<int>::max()) {
        return -1;
    }
    return result;
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    std::cout << "So xu toi thieu de doi " << amount << " (Top-Down DP): " << coinChangeMemo(amount, coins) << std::endl; // Expected: 3

    std::vector<int> coins2 = {1, 2, 5};
    int amount2 = 30; // Bây giờ có thể tính nhanh hơn nhiều!
    std::cout << "So xu toi thieu de doi " << amount2 << " (Top-Down DP): " << coinChangeMemo(amount2, coins2) << std::endl; // Expected: 6 (5*6)

    std::vector<int> coins3 = {2};
    int amount3 = 3; // Không thể đổi
    std::cout << "So xu toi thieu de doi " << amount3 << " (Top-Down DP): " << coinChangeMemo(amount3, coins3) << std::endl; // Expected: -1

     std::vector<int> coins4 = {1, 5};
    int amount4 = 7;
    std::cout << "So xu toi thieu de doi " << amount4 << " (Top-Down DP): " << coinChangeMemo(amount4, coins4) << std::endl; // Expected: 3 (5+1+1)

    return 0;
}

Giải thích code Top-Down DP:

• Ta thêm một tham số std::vector<int>& memo vào hàm đệ quy. Kích thước của memo là amount + 1, index i của memo sẽ lưu kết quả cho số tiền i.
• memo được khởi tạo với giá trị đặc biệt (-1) để biết ô nào chưa được tính.
• Dòng if (memo[amount] != -1) là điểm mấu chốt của memoization. Nếu kết quả cho amount đã có trong bảng (không phải -1), ta trả về ngay giá trị đã lưu.
• Nếu chưa có, ta tính toán như bình thường.
• Sau khi tính xong và trước khi trả về, ta lưu kết quả vào memo[amount] = min_count;.

Với memoization, mỗi bài toán con minCoins(i) (với 0 <= i <= amount) chỉ được tính một lần duy nhất. Độ phức tạp thời gian được cải thiện đáng kể. Với N là amount và M là số lượng mệnh giá đồng xu (coins.size()), mỗi trạng thái amount cần duyệt qua M đồng xu để tính toán. Vì có N+1 trạng thái (từ 0 đến N), tổng thời gian là O(N * M). Độ phức tạp không gian là O(N) cho mảng memo.

Cách tiếp cận 2: Bottom-Up DP (Tabulation)

Cách tiếp cận Bottom-Up thường dễ cài đặt bằng vòng lặp hơn là đệ quy và có thể tránh được overhead của các lời gọi hàm đệ quy. Chúng ta sẽ xây dựng bảng DP từ dưới lên.

Ta tạo một mảng dp có kích thước amount + 1, trong đó dp[i] sẽ lưu trữ số xu tối thiểu cần thiết để tạo thành số tiền i.

Khởi tạo:

• dp[0] = 0: Cần 0 xu để tạo thành số tiền 0.
• dp[i] = infinity (hoặc một giá trị rất lớn) cho tất cả các i > 0: Ban đầu, ta giả định không thể tạo thành các số tiền này.

Công thức chuyển trạng thái (Transition): Để tính dp[i] (số xu tối thiểu cho số tiền i), ta duyệt qua tất cả các mệnh giá đồng xu coin. Nếu i >= coin và dp[i - coin] không phải là infinity (tức là số tiền i - coin có thể đổi được), thì ta có thể đạt được số tiền i bằng cách thêm đồng xu coin vào lời giải cho i - coin. Do đó, ta cập nhật dp[i] bằng cách so sánh giá trị hiện tại với dp[i - coin] + 1. dp[i] = min(dp[i], dp[i - coin] + 1)

Ta sẽ lặp i từ 1 đến amount. Bên trong vòng lặp i, ta lặp qua từng coin.

#include <iostream>
#include <vector>
#include <algorithm> // For std::min
#include <limits>    // For std::numeric_limits

// Hàm Bottom-Up DP
int coinChangeTabulation(int amount, const std::vector<int>& coins) {
    // Tạo bảng DP có kích thước amount + 1
    // dp[i] sẽ lưu số xu tối thiểu để đổi số tiền i
    std::vector<int> dp(amount + 1, std::numeric_limits<int>::max());

    // Trường hợp cơ bản: cần 0 xu để đổi số tiền 0
    dp[0] = 0;

    // Lặp qua từng số tiền từ 1 đến amount
    for (int i = 1; i <= amount; ++i) {
        // Để tính dp[i], ta xem xét tất cả các mệnh giá đồng xu
        for (int coin : coins) {
            // Nếu số tiền hiện tại (i) đủ lớn để dùng đồng xu này (coin)
            // VÀ số tiền (i - coin) trước đó có thể đổi được (không phải max)
            if (i >= coin && dp[i - coin] != std::numeric_limits<int>::max()) {
                // Cập nhật dp[i]: chọn min giữa giá trị hiện tại
                // và (số xu để đổi i-coin) + 1 (cho đồng xu hiện tại)
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // Kết quả cuối cùng nằm ở dp[amount]
    // Nếu dp[amount] vẫn là giá trị lớn, tức là không thể đổi tiền
    if (dp[amount] == std::numeric_limits<int>::max()) {
        return -1;
    }
    return dp[amount];
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    std::cout << "So xu toi thieu de doi " << amount << " (Bottom-Up DP): " << coinChangeTabulation(amount, coins) << std::endl; // Expected: 3

    std::vector<int> coins2 = {1, 2, 5};
    int amount2 = 30;
    std::cout << "So xu toi thieu de doi " << amount2 << " (Bottom-Up DP): " << coinChangeTabulation(amount2, coins2) << std::endl; // Expected: 6

    std::vector<int> coins3 = {2};
    int amount3 = 3;
    std::cout << "So xu toi thieu de doi " << amount3 << " (Bottom-Up DP): " << coinChangeTabulation(amount3, coins3) << std::endl; // Expected: -1

     std::vector<int> coins4 = {1, 5};
    int amount4 = 7;
    std::cout << "So xu toi thieu de doi " << amount4 << " (Bottom-Up DP): " << coinChangeTabulation(amount4, coins4) << std::endl; // Expected: 3

    return 0;
}

Giải thích code Bottom-Up DP:

• Tạo dp vector kích thước amount + 1. dp[i] lưu số xu tối thiểu cho số tiền i. Khởi tạo dp[0] = 0, các phần tử khác bằng một số rất lớn (std::numeric_limits<int>::max()).
• Vòng lặp ngoài for (int i = 1; i <= amount; ++i): Duyệt qua tất cả các số tiền mục tiêu nhỏ dần, từ 1 đến amount. Ta đang cố gắng tìm dp[i].
• Vòng lặp trong for (int coin : coins): Với mỗi số tiền i, ta xem xét việc sử dụng từng mệnh giá coin.
• Điều kiện if (i >= coin && dp[i - coin] != std::numeric_limits<int>::max()): Ta chỉ có thể sử dụng coin nếu số tiền hiện tại i đủ lớn (i >= coin) và bài toán con i - coin đã có lời giải hợp lệ (dp[i - coin] không phải max).
• dp[i] = std::min(dp[i], dp[i - coin] + 1);: Nếu điều kiện trên thỏa mãn, ta có một cách để đạt được số tiền i là dùng 1 đồng xu coin và số xu tối thiểu cho i - coin. Ta so sánh số lượng xu này (dp[i - coin] + 1) với số lượng xu tối thiểu hiện tại đang lưu trong dp[i] và giữ lại giá trị nhỏ hơn.
• Cuối cùng, dp[amount] chứa kết quả mong muốn. Nếu nó vẫn là max, có nghĩa là không có cách nào để đổi tiền amount bằng các đồng xu đã cho.

Cách tiếp cận Bottom-Up DP có cùng độ phức tạp thời gian O(N * M) và độ phức tạp không gian O(N) như Top-Down DP, nhưng thường chạy nhanh hơn một chút trong thực tế do không có overhead của các lời gọi hàm đệ quy.

Bài toán đổi tiền: Phiên bản tìm số cách đổi tiền

Bây giờ, chúng ta hãy xem xét biến thể thứ hai của bài toán đổi tiền: Cho một tập hợp các mệnh giá đồng xu và một tổng số tiền mục tiêu Amount. Tìm tổng số cách khác nhau để tạo thành tổng số tiền Amount bằng cách sử dụng các đồng xu có sẵn (với số lượng không giới hạn). Thứ tự của các đồng xu không quan trọng (ví dụ: dùng {1, 2} và dùng {2, 1} để đổi 3 bằng xu {1, 2} được coi là một cách duy nhất).

Phiên bản này cũng có thể giải bằng Quy hoạch động Bottom-Up, nhưng công thức chuyển trạng thái sẽ khác.

Ta tạo một mảng dp có kích thước amount + 1, trong đó dp[i] sẽ lưu trữ số cách để tạo thành số tiền i.

Khởi tạo:

• dp[0] = 1: Có một cách duy nhất để tạo thành số tiền 0, đó là không dùng đồng xu nào.

Công thức chuyển trạng thái: Để tính dp[i] (số cách đổi tiền i), ta sẽ sử dụng từng loại đồng xu coin. Khi xử lý đồng xu coin, ta sẽ cộng số cách đổi tiền i - coin vào số cách đổi tiền i. dp[i] += dp[i - coin]

Lưu ý quan trọng: Để đảm bảo chúng ta đếm số tổ hợp các đồng xu chứ không phải số hoán vị, thứ tự của các vòng lặp rất quan trọng. Ta sẽ lặp qua các loại đồng xu trước, sau đó mới lặp qua các số tiền mà đồng xu đó có thể góp phần tạo nên.

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

// Hàm Bottom-Up DP để tìm số cách đổi tiền
int countChangeWays(int amount, const std::vector<int>& coins) {
    // Tạo bảng DP có kích thước amount + 1
    // dp[i] sẽ lưu số cách để đổi số tiền i
    std::vector<int> dp(amount + 1, 0);

    // Trường hợp cơ bản: có 1 cách để đổi số tiền 0 (không dùng xu nào)
    dp[0] = 1;

    // Lặp qua từng loại đồng xu có sẵn
    for (int coin : coins) {
        // Với mỗi đồng xu, lặp qua các số tiền từ giá trị của đồng xu đó
        // đến số tiền mục tiêu.
        // dp[i] sẽ được cập nhật bằng cách cộng số cách đổi tiền i - coin
        for (int i = coin; i <= amount; ++i) {
            // dp[i] = số cách đổi tiền i trước khi xét đồng xu 'coin'
            //       + số cách đổi tiền i - coin (khi thêm đồng xu 'coin')
            dp[i] += dp[i - coin];
        }
    }

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

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 5;
    // Các cách đổi 5:
    // 1+1+1+1+1
    // 1+1+1+2
    // 1+2+2
    // 1+1+3 (nếu có 3, nhưng không có)
    // 5
    // Tổng cộng: 4 cách ({1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5})
    std::cout << "So cach doi " << amount << " (DP): " << countChangeWays(amount, coins) << std::endl; // Expected: 4

    std::vector<int> coins2 = {2, 5, 10};
    int amount2 = 10;
    // Các cách đổi 10:
    // 2+2+2+2+2
    // 2+2+2+4 (nếu có 4)
    // 2+2+3+3 (nếu có 3)
    // 2+2+6 (nếu có 6)
    // 2+2+2+2+2
    // 2+2+2+4 (ko co 4)
    // 2+2+3+3 (ko co 3)
    // 2+2+6 (ko co 6)
    // 2+2+2+4 (ko co 4)
    // 2+2+6 (ko co 6)
    // 2+2+2+2+2 (1 cach)
    // 2+2+2+4 (ko co 4)
    // 2+2+3+3 (ko co 3)
    // 2+2+6 (ko co 6)
    // 2+2+8 (ko co 8)
    // 2+4+4 (ko co 4)
    // 2+8 (ko co 8)
    // 2+2+2+2+2
    // 2+2+2+4 (ko co 4)
    // 2+2+6 (ko co 6)
    // 2+2+8 (ko co 8)
    // 2+4+4 (ko co 4)
    // 2+6+2 -> {2,2,2,2,2} (1)
    // 2+2+2+4 (ko co 4)
    // 2+2+6 (ko co 6)
    // 2+2+8 (ko co 8)
    // 2+4+4 (ko co 4)
    // 2+6+2 (trung)
    // 2+2+...
    // {2,2,2,2,2}
    // {2,2,2,4} (ko co 4)
    // {2,2,6} (ko co 6)
    // {2,8} (ko co 8)
    // {5,5}
    // {10}
    // {2,2,2,2,2}
    // {2,2,2,4} -> ko co 4
    // {2,2,6} -> ko co 6
    // {2,8} -> ko co 8
    // {5,5}
    // {10}
    // {2,2,2,2,2}
    // {2,2,2,4} -> ko co 4
    // {2,2,6} -> ko co 6
    // {2,8} -> ko co 8
    // {5,5}
    // {10}
    // {2,2,2,2,2} -> 1
    // {2,2,2,4} -> ko co 4
    // {2,2,6} -> ko co 6
    // {2,8} -> ko co 8
    // {5,5} -> 1
    // {10} -> 1
    // {2,2,2,2,2} (1)
    // {2,2,2,4} (ko)
    // {2,2,6} (ko)
    // {2,8} (ko)
    // {5,5} (1)
    // {10} (1)
    // Cách tính đúng:
    // coins {2,5,10}, amount 10
    // dp[0]=1
    // Xet coin 2:
    // dp[2] += dp[0] = 1  ({2})
    // dp[4] += dp[2] = 1  ({2,2})
    // dp[6] += dp[4] = 1  ({2,2,2})
    // dp[8] += dp[6] = 1  ({2,2,2,2})
    // dp[10] += dp[8] = 1 ({2,2,2,2,2})
    // dp: [1,0,1,0,1,0,1,0,1,0,1]
    // Xet coin 5:
    // dp[5] += dp[0] = 1 ({5})
    // dp[7] += dp[2] = 1 ({5,2})
    // dp[10] += dp[5] = 1+1=2 ({2,2,2,2,2}, {5,5})
    // dp: [1,0,1,0,1,1,1,1,1,0,2]
    // Xet coin 10:
    // dp[10] += dp[0] = 2+1=3 ({2,2,2,2,2}, {5,5}, {10})
    // dp: [1,0,1,0,1,1,1,1,1,0,3]
    // Result for 10 is 3.
    std::cout << "So cach doi " << amount2 << " (DP): " << countChangeWays(amount2, coins2) << std::endl; // Expected: 3

    std::vector<int> coins3 = {3};
    int amount3 = 2;
     std::cout << "So cach doi " << amount3 << " (DP): " << countChangeWays(amount3, coins3) << std::endl; // Expected: 0

    return 0;
}

Giải thích code Số cách đổi tiền:

• Tạo dp vector kích thước amount + 1. dp[i] lưu số cách để đổi số tiền i. Khởi tạo dp với 0, riêng dp[0] = 1.
• Vòng lặp ngoài for (int coin : coins): Duyệt qua TỪNG loại đồng xu. Thứ tự của các đồng xu không quan trọng cho tính đúng đắn, nhưng ảnh hưởng đến thứ tự cập nhật trong bảng.
• Vòng lặp trong for (int i = coin; i <= amount; ++i): Với mỗi coin, ta duyệt qua các số tiền mà coin có thể giúp tạo thành, bắt đầu từ chính giá trị của coin (i = coin). Ta đi lên đến amount.
• dp[i] += dp[i - coin];: Đây là công thức chuyển trạng thái. Số cách đổi tiền i được tăng thêm số cách đổi tiền cho i - coin bằng cách thêm một đồng xu coin vào mỗi tổ hợp của i - coin.
• Tại sao lại lặp qua coin trước rồi mới đến i? Hãy xem xét đổi tiền 3 với xu {1, 2}.
  • dp khởi tạo: [1, 0, 0, 0]
  • Xét xu 1:
    • i=1: dp[1] += dp[0] (1+0) = 1. dp: [1, 1, 0, 0] ({1})
    • i=2: dp[2] += dp[1] (0+1) = 1. dp: [1, 1, 1, 0] ({1,1})
    • i=3: dp[3] += dp[2] (0+1) = 1. dp: [1, 1, 1, 1] ({1,1,1})
  • Xét xu 2:
    • i=2: dp[2] += dp[0] (1+1) = 2. dp: [1, 1, 2, 1] ({1,1}, {2}) -> dp[2] bây giờ có 2 cách.
    • i=3: dp[3] += dp[1] (1+1) = 2. dp: [1, 1, 2, 2] ({1,1,1}, {2,1}) -> dp[3] bây giờ có 2 cách.
  • Kết quả dp[3] là 2. Các cách là {1,1,1} và {2,1}. Ơ, thiếu {1,2}!
  • Wait, {2,1} và {1,2} thường được coi là MỘT cách trong bài toán số cách đổi tiền nếu không quan tâm thứ tự.
  • Cách giải thích công thức dp[i] += dp[i - coin] khi lặp coin trước, rồi i: Khi ta xử lý coin hiện tại, dp[i - coin] chứa số cách đổi tiền i - coin chỉ sử dụng các đồng xu ĐÃ XÉT trước coin hiện tại. Bằng cách cộng dp[i - coin] vào dp[i], ta đang thêm TẤT CẢ các tổ hợp của i - coin (chỉ dùng các xu trước hoặc bằng coin) VÀO MỖI tổ hợp của i chỉ dùng các xu trước coin. Điều này đảm bảo mỗi tổ hợp được đếm chính xác một lần.
  • Hãy thử lại với coins {1, 2}, amount 3, nhưng lặp coin trước rồi i:
    • dp khởi tạo: [1, 0, 0, 0]
    • Xét xu 1:
      • i=1: dp[1] += dp[0] = 1 ([1,1,0,0])
      • i=2: dp[2] += dp[1] = 1 ([1,1,1,0])
      • i=3: dp[3] += dp[2] = 1 ([1,1,1,1])
    • dp sau xu 1: [1, 1, 1, 1] ({}, {1}, {1,1}, {1,1,1})
    • Xét xu 2:
      • i=2: dp[2] += dp[2-2] = dp[0] = 1. dp[2] = 1 + 1 = 2. ([1,1,2,1]) ({1,1}, {2})
      • i=3: dp[3] += dp[3-2] = dp[1] = 1. dp[3] = 1 + 1 = 2. ([1,1,2,2]) ({1,1,1}, {1,2})
    • Kết quả dp[3] là 2. Các cách là {1,1,1} và {1,2}. Vẫn thiếu {2,1} nếu thứ tự quan trọng. Nhưng nếu thứ tự không quan trọng, thì {1,2} và {2,1} là một. Tuy nhiên, với coins {1,2}, amount 3, các tổ hợp là {1,1,1} và {1,2}. DP này đếm được 2.
    • Ví dụ coins {1,2,5}, amount 5:
      • dp khởi tạo: [1,0,0,0,0,0]
      • Xu 1: [1,1,1,1,1,1] ({}, {1}, {1,1}, {1,1,1}, {1,1,1,1}, {1,1,1,1,1})
      • Xu 2:
        • i=2: dp[2]+=dp[0] = 1+1=2 ({1,1}, {2})
        • i=3: dp[3]+=dp[1] = 1+1=2 ({1,1,1}, {1,2})
        • i=4: dp[4]+=dp[2] = 1+2=3 ({1,1,1,1}, {1,1,2}, {2,2})
        • i=5: dp[5]+=dp[3] = 1+2=3 ({1,1,1,1,1}, {1,1,1,2}, {1,2,2})
      • dp sau xu 2: [1,1,2,2,3,3]
      • Xu 5:
        • i=5: dp[5]+=dp[0] = 3+1=4 ({1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5})
      • dp sau xu 5: [1,1,2,2,3,4]
    • Kết quả dp[5] là 4. Đây là cách đếm tổ hợp CHUẨN.

Độ phức tạp thời gian và không gian cho phiên bản này cũng là O(N * M) và O(N) tương ứng.

Bài tập ví dụ:

Số nguyên lớn.

Cho hai số nguyên lớn N và M có không quá 1000 chữ số. Người ta muốn tính xem liệu có thể lấy ra nhiều nhất bao nhiêu chữ số trong N (không cần liên tiếp) và giữ nguyên thứ tự của nó để tạo ra một số X sao cho ta cũng có thể tìm thấy X trong số M theo cách tương tự.

Input Format

Dòng thứ nhất ghi số N, dòng thứ 2 ghi số M.(1<=len(N), len(M) <= 1000)

Constraints

.

Output Format

In ra số chữ số nhiều nhất có thể của X.

Ví dụ:

Dữ liệu vào

1235176433
45412231359760

Dữ liệu ra

6

Bài toán này là biến thể của bài toán tìm dãy con chung dài nhất (Longest Common Subsequence - LCS) giữa hai chuỗi.

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

1. Sử dụng phương pháp Quy hoạch động (Dynamic Programming).
2. Xây dựng một bảng dp[i][j] kích thước (len(N)+1) x (len(M)+1), trong đó dp[i][j] là độ dài dãy con chung dài nhất của N[0...i-1] và M[0...j-1].
3. Khởi tạo bảng dp với giá trị 0.
4. Duyệt qua các chữ số của N (từ i=1 đến len(N)) và M (từ j=1 đến len(M)).
5. Tại mỗi bước (i, j):
   • Nếu chữ số thứ i-1 của N bằng chữ số thứ j-1 của M, thì dp[i][j] = dp[i-1][j-1] + 1. (Mở rộng dãy con chung)
   • Ngược lại, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). (Lấy kết quả tốt nhất từ việc loại bỏ một chữ số ở cuối N hoặc M)
6. Kết quả cuối cùng là giá trị tại dp[len(N)][len(M)].

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