Bài 26.3. Dãy con chung dài nhất (LCS)

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau "giải mã" một bài toán kinh điển và vô cùng thú vị, đó là tìm _Dãy con chung dài nhất_ (Longest Common Subsequence - LCS) của hai chuỗi hoặc hai dãy cho trước. Bài toán này không chỉ là nền tảng quan trọng trong lập trình thi đấu mà còn có rất nhiều ứng dụng thực tế, từ so sánh gen trong sinh học đến công cụ so sánh file (diff) trong lập trình.

Hãy bắt đầu hành trình khám phá LCS!

Dãy con (Subsequence) là gì?

Trước khi đi vào _dãy con chung_ (Common Subsequence), chúng ta cần hiểu rõ _dãy con_ (Subsequence). Một dãy con của một dãy ban đầu được tạo ra bằng cách _xóa đi không hoặc nhiều phần tử_ từ dãy ban đầu mà _không làm thay đổi thứ tự_ của các phần tử còn lại.

Ví dụ:

Dãy ban đầu: A = {A, B, C, D, E}

Các dãy con của A có thể là:

  • {A, C, E} (xóa B, D)
  • {B, D} (xóa A, C, E)
  • {A, B, C, D, E} (xóa 0 phần tử - chính nó là dãy con của chính nó)
  • {} (xóa tất cả phần tử - dãy rỗng)
  • {A}
  • {E}

Các dãy sau _không_ phải là dãy con của A:

  • {A, C, B} (thứ tự bị thay đổi)
  • {F} (chứa phần tử không có trong A)

Điều quan trọng cần nhớ là: _dãy con khác với dãy con liên tục (substring hay contiguous subsequence)_. Dãy con liên tục yêu cầu các phần tử phải đứng cạnh nhau trong dãy gốc.

Dãy con chung (Common Subsequence) là gì?

_Dãy con chung_ của hai dãy $X$ và $Y$ là một dãy $Z$ mà $Z$ vừa là dãy con của $X$, vừa là dãy con của $Y$.

Ví dụ:

Dãy $X = {A, B, C, B, D, A, B}$ Dãy $Y = {B, D, C, A, B, A}$

Một số dãy con chung của X và Y là:

  • {B}
  • {A, B}
  • {B, C, A} (có trong X: A, B, C, B, A, B; có trong Y: B, D, C, A, B, A)
  • {B, D, A, B} (có trong X: A, B, C, B, D, A, B; có trong Y: B, D, C, A, B, A)

Bài toán Dãy con chung dài nhất (LCS)

Bài toán _Dãy con chung dài nhất_ (LCS) yêu cầu chúng ta tìm một dãy con chung của hai dãy $X$ và $Y$ sao cho dãy con chung đó có _độ dài lớn nhất_.

Ví dụ (tiếp theo):

Dãy $X = {A, B, C, B, D, A, B}$ Dãy $Y = {B, D, C, A, B, A}$

Như ví dụ trên, các dãy con chung có thể là {B}, {A, B}, {B, C, A}, {B, D, A, B}. Độ dài của chúng lần lượt là 1, 2, 3, 4.

Trong trường hợp này, các dãy con chung dài nhất là {B, D, A, B} và {B, C, A, B} (có trong X: A, B, C, B, A, B; có trong Y: B, D, C, A, B, A - oops, trong Y không có A sau C... thử lại)

Dãy $X = {A, B, C, B, D, A, B}$ Dãy $Y = {B, D, C, A, B, A}$

Dãy con chung {B, D, A, B}:

  • Trong X: A, B, C, B, D, A, B (Indices: 1, 3, 4, 6)
  • Trong Y: B, D, C, A, B, A (Indices: 0, 1, 3, 4) Độ dài 4. Đây là một LCS.

Dãy con chung {B, C, A, B}:

  • Trong X: A, B, C, B, D, A, B (Indices: 1, 2, 6) -> Không được, thiếu B sau A. Thử lại.
  • Trong X: A, B, C, B, D, A, B (Indices: 1, 2, 5, 6)
  • Trong Y: B, D, C, A, B, A (Indices: 0, 2, 3, 4) Độ dài 4. Đây cũng là một LCS.

Vậy, bài toán là tìm _độ dài_ của LCS, và _một_ hoặc _tất cả_ các LCS đó.

Tại sao LCS lại khó một cách "ngây thơ"?

Nếu chúng ta cố gắng tìm LCS bằng cách liệt kê tất cả các dãy con của một dãy (giả sử $X$) và kiểm tra xem chúng có phải là dãy con của dãy kia ($Y$) hay không, rồi chọn ra dãy dài nhất. Số lượng dãy con của một dãy có độ dài $n$ là $2^n$. Với $n$ chỉ vài chục, con số này đã cực kỳ lớn, khiến cách tiếp cận này không khả thi về mặt thời gian.

Chúng ta cần một phương pháp hiệu quả hơn. Và đây chính là lúc _Lập trình Động (Dynamic Programming)_ tỏa sáng!

Giải quyết bài toán LCS bằng Lập trình Động (Dynamic Programming)

Bài toán LCS có đầy đủ hai tính chất cần thiết cho Lập trình Động:

  1. _Cấu trúc con tối ưu (Optimal Substructure):_ Giải pháp tối ưu cho bài toán lớn có thể được xây dựng từ giải pháp tối ưu của các bài toán con.
  2. _Các bài toán con gối chồng (Overlapping Subproblems):_ Các bài toán con được giải đi giải lại nhiều lần.

Chúng ta sẽ định nghĩa bài toán con và xây dựng công thức truy hồi.

Gọi LCS(i, j) là độ dài của dãy con chung dài nhất của hai tiền tố (prefix):

  • Tiền tố độ dài i của dãy $X$ (ký hiệu $X[0...i-1]$)
  • Tiền tố độ dài j của dãy $Y$ (ký hiệu $Y[0...j-1]$)

Mục tiêu của chúng ta là tìm LCS(m, n), trong đó $m$ là độ dài của $X$ và $n$ là độ dài của $Y$.

Bây giờ, hãy xem xét cách tính LCS(i, j) dựa trên các bài toán con nhỏ hơn:

Có hai trường hợp xảy ra khi xem xét ký tự cuối cùng của hai tiền tố $X[0...i-1]$ và $Y[0...j-1]$ (tức là ký tự $X[i-1]$ và $Y[j-1]$):

  • Trường hợp 1: Ký tự cuối cùng khớp nhau ($X[i-1] == Y[j-1]$) Nếu ký tự cuối cùng của hai tiền tố giống nhau, thì ký tự này chắc chắn có thể là phần tử cuối cùng của một dãy con chung dài nhất. Khi đó, độ dài của LCS(i, j) sẽ bằng độ dài của LCS của hai tiền tố ngắn hơn (bỏ đi ký tự cuối cùng vừa khớp) cộng thêm 1 (cho ký tự vừa khớp). Công thức: LCS(i, j) = LCS(i-1, j-1) + 1

  • Trường hợp 2: Ký tự cuối cùng không khớp nhau ($X[i-1] != Y[j-1]$) Nếu ký tự cuối cùng của hai tiền tố khác nhau, thì ký tự $X[i-1]$ và $Y[j-1]$ không thể cùng lúc là phần tử cuối cùng của một dãy con chung dài nhất. Khi đó, dãy con chung dài nhất của $X[0...i-1]$ và $Y[0...j-1]$ phải là LCS của:

    • $X[0...i-2]$ và $Y[0...j-1]$ (bỏ $X[i-1]$)
    • Hoặc $X[0...i-1]$ và $Y[0...j-2]$ (bỏ $Y[j-1]$) Chúng ta cần lấy giá trị lớn nhất trong hai trường hợp này. Công thức: LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

Trường hợp cơ sở (Base Cases):

Khi một trong hai tiền tố rỗng (độ dài 0), thì dãy con chung dài nhất với tiền tố còn lại (hoặc rỗng) chắc chắn là dãy rỗng, có độ dài 0. LCS(i, 0) = 0 cho mọi $i \ge 0$. LCS(0, j) = 0 cho mọi $j \ge 0$.

Kết hợp lại, chúng ta có công thức truy hồi cho LCS(i, j):

  • Nếu $i=0$ hoặc $j=0$: LCS(i, j) = 0
  • Nếu $X[i-1] == Y[j-1]$: LCS(i, j) = LCS(i-1, j-1) + 1
  • Nếu $X[i-1] != Y[j-1]$: LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

Chúng ta có thể sử dụng một bảng (thường là mảng 2 chiều dp[m+1][n+1]) để lưu trữ các giá trị LCS(i, j) đã tính được, tránh tính toán lặp lại các bài toán con gối chồng. Bảng này sẽ được điền từ trên xuống dưới, từ trái sang phải.

Xây dựng bảng DP (Minh họa)

Xét hai chuỗi: $X = \text{"AGTAB"}$ ($m=5$) $Y = \text{"GXTAYB"}$ ($n=6$)

Chúng ta tạo bảng dp[6][7] (kích thước $(m+1) \times (n+1)$) và khởi tạo hàng 0 và cột 0 bằng 0.

"" A G T A B
"" 0 0 0 0 0 0 0
A 0
G 0
T 0
A 0
B 0

Bây giờ, chúng ta điền bảng theo công thức truy hồi. dp[i][j] tương ứng với X[i-1] và Y[j-1].

  • dp[1][1] (X[0] == 'A', Y[0] == 'G'): Không khớp. max(dp[0][1], dp[1][0]) = max(0, 0) = 0.
  • dp[1][2] (X[0] == 'A', Y[1] == 'X'): Không khớp. max(dp[0][2], dp[1][1]) = max(0, 0) = 0.
  • ...
  • dp[1][4] (X[0] == 'A', Y[3] == 'A'): Khớp! dp[1][4] = dp[0][3] + 1 = 0 + 1 = 1.

Tiếp tục điền bảng:

"" G X T A Y B
"" 0 0 0 0 0 0 0
A 0 0 0 0 _1_ 1 1
G 0 _1_ 1 1 1 1 1
T 0 1 1 _2_ 2 2 2
A 0 1 1 2 _3_ 3 3
B 0 1 1 2 3 3 _4_

Giải thích một vài ô:

  • dp[2][1] (X[1] == 'G', Y[0] == 'G'): Khớp! dp[2][1] = dp[1][0] + 1 = 0 + 1 = 1.
  • dp[3][4] (X[2] == 'T', Y[3] == 'A'): Không khớp. max(dp[2][4], dp[3][3]) = max(1, 2) = 2.
  • dp[4][5] (X[3] == 'A', Y[4] == 'Y'): Không khớp. max(dp[3][5], dp[4][4]) = max(2, 3) = 3.
  • dp[5][6] (X[4] == 'B', Y[5] == 'B'): Khớp! dp[5][6] = dp[4][5] + 1 = 3 + 1 = 4.

Giá trị cuối cùng dp[m][n] (ở đây là dp[5][6]) chính là độ dài của LCS. Trong ví dụ này, độ dài LCS là 4.

Các LCS có thể là: "GTAB", "ATAB". Cả hai đều có độ dài 4.

Cài đặt bằng C++ (Tính độ dài)

Chúng ta có thể cài đặt việc điền bảng DP để tính độ dài LCS như sau:

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

// Hàm tính độ dài Dãy con chung dài nhất (LCS)
int lcsLength(const std::string& s1, const std::string& s2) {
    int m = s1.length();
    int n = s2.length();

    // Tạo bảng DP có kích thước (m+1) x (n+1) và khởi tạo bằng 0
    // dp[i][j] sẽ lưu trữ độ dài LCS của s1[0...i-1] và s2[0...j-1]
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // Điền bảng DP
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // Nếu ký tự cuối cùng của hai tiền tố khớp nhau
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // Nếu không khớp nhau
            else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Giá trị ở góc dưới cùng bên phải của bảng là độ dài LCS của toàn bộ s1 và s2
    return dp[m][n];
}

// int main() {
//     std::string s1 = "AGTAB";
//     std::string s2 = "GXTAYB";
//     std::cout << "Chuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "Do dai LCS: " << lcsLength(s1, s2) << std::endl; // Output: 4

//     s1 = "ABCBDAB";
//     s2 = "BDCAB";
//     std::cout << "\nChuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "Do dai LCS: " << lcsLength(s1, s2) << std::endl; // Output: 4

//     s1 = "ABC";
//     s2 = "DEF";
//     std::cout << "\nChuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "Do dai LCS: " << lcsLength(s1, s2) << std::endl; // Output: 0

//     s1 = "AAAA";
//     s2 = "AA";
//     std::cout << "\nChuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "Do dai LCS: " << lcsLength(s1, s2) << std::endl; // Output: 2

//     return 0;
// }

Giải thích Code:

  • Chúng ta sử dụng std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0)); để tạo bảng DP. Kích thước là (m+1) x (n+1) để xử lý các trường hợp cơ sở (tiền tố rỗng) dễ dàng hơn, tương ứng với chỉ số 0 trong mảng 2D.
  • Vòng lặp lồng nhau for (int i = 1; i <= m; ++i) và for (int j = 1; j <= n; ++j) duyệt qua tất cả các cặp tiền tố có độ dài từ 1 đến m và n.
  • Trong vòng lặp, chúng ta kiểm tra ký tự cuối cùng của tiền tố hiện tại: s1[i - 1] (ký tự ở vị trí i-1 trong chuỗi gốc s1, tương ứng với tiền tố độ dài i) và s2[j - 1].
  • Nếu khớp (s1[i - 1] == s2[j - 1]), giá trị dp[i][j] bằng dp[i - 1][j - 1] (LCS của tiền tố ngắn hơn 1 ký tự ở cả hai chuỗi) cộng thêm 1.
  • Nếu không khớp, dp[i][j] bằng giá trị lớn nhất giữa dp[i - 1][j] (bỏ ký tự cuối của s1) và dp[i][j - 1] (bỏ ký tự cuối của s2).
  • Cuối cùng, dp[m][n] chứa độ dài LCS của toàn bộ hai chuỗi s1 và s2.

Độ phức tạp về thời gian của giải thuật này là _O(m*n)_ vì chúng ta điền một bảng có kích thước $(m+1) \times (n+1)$, và mỗi ô mất thời gian _O(1)_ để tính toán. Độ phức tạp về không gian là _O(m*n)_ để lưu trữ bảng DP. (Lưu ý: Nếu chỉ cần độ dài chứ không cần truy vết LCS, có thể giảm không gian xuống _O(min(m,n))_ bằng cách chỉ lưu trữ 2 hàng hoặc 2 cột gần nhất).

Truy vết để lấy lại Dãy con chung dài nhất

Bảng DP không chỉ cho chúng ta độ dài LCS mà còn giúp chúng ta _truy vết (backtrack)_ để xây dựng lại một (hoặc nhiều) dãy con chung dài nhất.

Chúng ta bắt đầu từ ô dp[m][n] (góc dưới cùng bên phải) và di chuyển ngược lên/sang trái dựa vào giá trị của các ô lân cận và công thức truy hồi:

  1. Bắt đầu từ i = m, j = n.
  2. Trong khi i > 0 và j > 0:
    • Nếu s1[i - 1] == s2[j - 1]: Điều này có nghĩa là ký tự này là một phần của LCS. Thêm s1[i - 1] (hoặc s2[j - 1]) vào kết quả và di chuyển chéo lên trên-trái: i--, j--.
    • Nếu s1[i - 1] != s2[j - 1]: Ký tự này không phải là phần của LCS. Chúng ta cần di chuyển đến ô mà từ đó giá trị dp[i][j] được suy ra.
      • Nếu dp[i - 1][j] > dp[i][j - 1]: Nghĩa là giá trị dp[i][j] đến từ việc bỏ ký tự cuối của s1. Di chuyển lên trên: i--.
      • Ngược lại (dp[i][j - 1] >= dp[i - 1][j]): Nghĩa là giá trị dp[i][j] đến từ việc bỏ ký tự cuối của s2. Di chuyển sang trái: j--. (Trường hợp dp[i-1][j] == dp[i][j-1] có thể đi theo hướng nào cũng được, chúng ta thường chọn một hướng cố định, ví dụ sang trái j--, để có được một LCS cụ thể).
  3. Khi i == 0 hoặc j == 0, chúng ta đã đi hết đường và xây dựng xong LCS (theo chiều ngược).

Vì chúng ta xây dựng LCS từ cuối về đầu, kết quả cuối cùng cần được đảo ngược.

Cài đặt bằng C++ (Truy vết và lấy LCS)

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

// Hàm tính và trả về một Dãy con chung dài nhất (LCS)
std::string lcsString(const std::string& s1, const std::string& s2) {
    int m = s1.length();
    int n = s2.length();

    // Tạo và điền bảng DP để tính độ dài LCS (giống như hàm lcsLength)
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Bảng DP đã được điền. Bây giờ thực hiện truy vết.
    std::string lcs = "";
    int i = m;
    int j = n;

    while (i > 0 && j > 0) {
        // Nếu ký tự cuối cùng khớp nhau (chúng ta đã đến từ ô chéo)
        if (s1[i - 1] == s2[j - 1]) {
            lcs += s1[i - 1]; // Thêm ký tự vào LCS
            i--; // Di chuyển chéo lên trên
            j--; // Di chuyển chéo sang trái
        }
        // Nếu không khớp, kiểm tra xem giá trị lớn hơn đến từ đâu (ô trên hay ô bên trái)
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--; // Di chuyển lên trên (do bỏ ký tự cuối của s1 cho LCS dài hơn)
        } else {
            j--; // Di chuyển sang trái (do bỏ ký tự cuối của s2 cho LCS dài hơn hoặc bằng)
        }
    }

    // LCS được xây dựng theo chiều ngược, cần đảo ngược chuỗi kết quả
    std::reverse(lcs.begin(), lcs.end());

    return lcs;
}

// int main() {
//     std::string s1 = "AGTAB";
//     std::string s2 = "GXTAYB";
//     std::cout << "Chuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "LCS (mot trong cac LCS): " << lcsString(s1, s2) << std::endl; // Output: GTAB (hoặc ATAB tùy cách truy vết)

//     s1 = "ABCBDAB";
//     s2 = "BDCAB";
//     std::cout << "\nChuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "LCS (mot trong cac LCS): " << lcsString(s1, s2) << std::endl; // Output: BDCAB (nếu luôn ưu tiên j--) hoặc BCAB, BDAB tùy đường đi cụ thể

//     s1 = "ABC";
//     s2 = "DEF";
//     std::cout << "\nChuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "LCS (mot trong cac LCS): " << lcsString(s1, s2) << std::endl; // Output: ""

//     s1 = "AAAA";
//     s2 = "AA";
//     std::cout << "\nChuoi 1: " << s1 << std::endl;
//     std::cout << "Chuoi 2: " << s2 << std::endl;
//     std::cout << "LCS (mot trong cac LCS): " << lcsString(s1, s2) << std::endl; // Output: AA

//     return 0;
// }

Giải thích Code Truy Vết:

  • Hàm lcsString đầu tiên tính toán và điền đầy đủ bảng DP, giống như hàm lcsLength. Chúng ta cần toàn bộ bảng để thực hiện truy vết.
  • Chúng ta khởi tạo một chuỗi rỗng lcs để lưu kết quả.
  • Sử dụng hai biến i và j bắt đầu từ m và n.
  • Vòng lặp while (i > 0 && j > 0) tiếp tục truy vết cho đến khi chạm vào hàng hoặc cột 0 của bảng DP (tức là một trong hai tiền tố trở thành rỗng).
  • Bên trong vòng lặp, chúng ta kiểm tra lại điều kiện của công thức truy hồi, nhưng theo hướng ngược lại:
    • Nếu s1[i - 1] == s2[j - 1]: Điều này chỉ xảy ra khi dp[i][j] được tính từ dp[i-1][j-1] + 1. Ký tự s1[i - 1] (hoặc s2[j-1]) là một phần của LCS. Chúng ta thêm nó vào chuỗi lcs và di chuyển đến ô dp[i-1][j-1].
    • Nếu không khớp, chúng ta dựa vào giá trị trong bảng DP để biết phải di chuyển đi đâu:
      • Nếu dp[i - 1][j] > dp[i][j - 1]: Nghĩa là dp[i][j] bằng dp[i - 1][j]. Điều này xảy ra khi chúng ta bỏ ký tự cuối của s1. Để truy vết LCS, chúng ta di chuyển lên ô dp[i-1][j] bằng cách giảm i.
      • Ngược lại (dp[i - 1][j] <= dp[i][j - 1]): Nghĩa là dp[i][j] bằng dp[i][j - 1]. Điều này xảy ra khi chúng ta bỏ ký tự cuối của s2. Để truy vết LCS, chúng ta di chuyển sang ô dp[i][j-1] bằng cách giảm j. (Lưu ý: nếu dp[i-1][j] == dp[i][j-1], cả hai hướng đều có thể dẫn đến một LCS có cùng độ dài. Việc chọn một hướng cố định sẽ cho ra một LCS cụ thể).
  • Chuỗi lcs được xây dựng từ cuối về đầu, nên sau khi vòng lặp kết thúc, chúng ta sử dụng std::reverse để đảo ngược chuỗi và nhận được LCS theo đúng thứ tự.

Độ phức tạp của phần truy vết là _O(m+n)_ vì trong mỗi bước, ít nhất một trong hai chỉ số i hoặc j giảm đi 1. Tổng độ phức tạp của lcsString vẫn là _O(m*n)_ do thời gian xây dựng bảng DP chiếm ưu thế. Độ phức tạp về không gian vẫn là _O(m*n)_ để lưu trữ bảng DP.

Các Ứng dụng của LCS

Bài toán LCS có nhiều ứng dụng thực tế quan trọng:

  • Tin sinh học: So sánh chuỗi DNA hoặc protein để tìm điểm tương đồng và mối quan hệ tiến hóa.
  • Công cụ diff: Các công cụ so sánh file (như diff trên Unix) sử dụng LCS để tìm ra các dòng đã bị thay đổi, thêm hoặc xóa giữa hai phiên bản của một file văn bản.
  • Kiểm tra đạo văn: Có thể sử dụng các kỹ thuật dựa trên LCS để so sánh văn bản và phát hiện các đoạn giống nhau.
  • Hệ thống gợi ý: Trong một số trường hợp, có thể dùng LCS để so sánh hành vi của người dùng (chuỗi các thao tác) và gợi ý nội dung tương tự.

Bài tập ví dụ:

Đổi Tiền.

Ngân hàng MB hiện có N tờ tiền có mệnh giá khác nhau được lưu vào mảng C[], bạn hãy tìm cách đổi số tiền là S sao cho số tờ tiền cần dùng là ít nhất. Bạn được sử dụng một mệnh giá không giới hạn số lần.

Input Format

Dòng đầu tiên chứa 2 số N và S; Dòng thứ 2 chưa N số là mệnh giá các tờ tiền.(1<=N<=100; 1<=S<=10^6; 1<=C[i]<=10^6)

Constraints

.

Output Format

In ra số tờ tiền nhỏ nhất cần đổi. Nếu không thể đổi được số tiền đúng bằng S thì in ra -1.

Ví dụ:

Dữ liệu vào
5 13
5 11 10 4 3
Dữ liệu ra
2

Bài này là bài toán Đổi Tiền kinh điển với số lượng tờ tiền của mỗi mệnh giá là không giới hạn. Đây là một bài toán tối ưu, có thể giải quyết bằng Quy hoạch động (Dynamic Programming).

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

  1. Xác định trạng thái DP: Gọi dp[i] là số lượng tờ tiền ít nhất để đổi được số tiền là i.
  2. Khởi tạo:
    • dp[0] = 0 (cần 0 tờ tiền để đổi 0).
    • Khởi tạo tất cả các dp[i] khác (với i > 0) bằng một giá trị rất lớn (đại diện cho vô cực), ví dụ S + 1 hoặc giá trị lớn nhất của kiểu dữ liệu integer (INT_MAX trong C++). Giá trị này biểu thị rằng ban đầu chúng ta chưa biết cách đổi số tiền i hoặc không thể đổi được.
  3. Công thức chuyển trạng thái: Để tính dp[i], ta xem xét việc sử dụng từng loại tờ tiền c có trong mảng C. Nếu ta sử dụng một tờ tiền mệnh giá c để đổi số tiền i, thì số tiền còn lại cần đổi là i - c. Số tờ tiền cần dùng trong trường hợp này sẽ là 1 + dp[i - c]. Ta muốn tìm cách đổi i sao cho số tờ tiền ít nhất, vì vậy: dp[i] = min(dp[i], 1 + dp[i - c]) Công thức này được áp dụng cho tất cả các mệnh giá c trong mảng C sao cho i >= c và dp[i - c] không phải là giá trị vô cực (nghĩa là số tiền i - c có thể đổi được).
  4. Lặp và tính toán: Duyệt i từ 1 đến S. Với mỗi giá trị i, duyệt qua tất cả các mệnh giá c trong mảng C. Áp dụng công thức chuyển trạng thái nếu điều kiện i >= c được thỏa mãn và dp[i-c] không phải vô cực.
  5. Kết quả: Sau khi hoàn thành việc tính toán cho tất cả các giá trị i đến S, kết quả là dp[S].
  6. Xử lý trường hợp không đổi được: Nếu sau khi tính toán, dp[S] vẫn giữ nguyên giá trị vô cực ban đầu, điều đó có nghĩa là không thể đổi được số tiền S bằng các mệnh giá đã cho. In ra -1. Ngược lại, in ra dp[S].

Lưu ý khi cài đặt:

  • Sử dụng một mảng dp có kích thước S + 1.
  • Cẩn thận với giá trị vô cực khi cộng thêm 1 để tránh tràn số (overflow) nếu sử dụng INT_MAX. Sử dụng S + 1 làm giá trị vô cực là an toàn hơn vì dp[i - c] + 1 sẽ không vượt quá S nếu i-c < S, và nếu dp[i-c] là S+1 thì dp[i-c]+1 sẽ lớn hơn S+1.
  • Vòng lặp ngoài duyệt qua tổng tiền i từ 1 đến S, vòng lặp trong duyệt qua các mệnh giá c.

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

Khóa học liên quan

Khoá học lập trình Python Giảm giá!
Ưu đãi có hạn
Khoá học lập trình Python
4.8 120 giờ
3300000 4500000
Học Ngay

Comments

There are no comments at the moment.