Chúng ta được cung cấp hai chuỗi, giả sử str1 và str2 chứa các ký tự và nhiệm vụ là tính toán các chuỗi con chung trong cả hai chuỗi. Trong chương trình dưới đây, chúng tôi đang sử dụng lập trình động và vì vậy chúng tôi cần biết lập trình động là gì và nó có thể được sử dụng ở những vấn đề nào.
Cách tiếp cận lập trình động tương tự như chia và chinh phục trong việc chia nhỏ vấn đề thành các vấn đề con nhỏ hơn và có thể nhỏ hơn. Nhưng không giống như, phân chia và chinh phục, các bài toán con này không được giải quyết một cách độc lập. Thay vào đó, kết quả của các bài toán con nhỏ hơn này được ghi nhớ và sử dụng cho các bài toán con tương tự hoặc chồng chéo.
Lập trình động được sử dụng khi chúng ta gặp vấn đề, có thể được chia thành các bài toán con tương tự để có thể sử dụng lại kết quả của chúng. Hầu hết, các thuật toán này được sử dụng để tối ưu hóa. Trước khi giải bài toán con trong tay, các thuật toán động sẽ cố gắng kiểm tra kết quả của các bài toán con đã giải trước đó. Các giải pháp của các vấn đề phụ được kết hợp để đạt được giải pháp tốt nhất.
Vì vậy, chúng ta có thể nói rằng -
Input − string str1 = “abc” String str2 = “ab” Output − count is 3
Giải thích - Từ các chuỗi đã cho, các dãy con chung được tạo thành là:{‘a’, ‘b’, ‘ab’}.
Input − string str1 = “ajblqcpdz” String str2 = “aefcnbtdi” Output − count is 11
Các chuỗi con phổ biến là - Từ các chuỗi đã cho, các dãy con chung được hình thành là:{“a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ac”, “cd”, “Abd” , “Acd”}
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập hai chuỗi, giả sử str1 và str2.
-
Tính độ dài của chuỗi đã cho bằng cách sử dụng hàm length () sẽ trả về một giá trị nguyên theo số ký tự trong một chuỗi và lưu trữ nó trong len1 cho str1 và trong len2 cho str2.
-
Tạo mảng 2-D để triển khai lập trình động, giả sử arr [len1 + 1] [len2 + 1]
-
Bắt đầu vòng lặp cho tôi đến 0 cho đến khi tôi nhỏ hơn len1
-
Vòng lặp bên trong, bắt đầu một vòng lặp khác cho j đến 0 cho đến khi j nhỏ hơn len2
-
Vòng lặp bên trong, kiểm tra IF str1 [i-1] =str2 [j-1] rồi đặt arr [i] [j] =1 + arr [i] [j-1] + arr [i-1] [j]
-
Nếu không, sau đó đặt arr [i] [j] =arr [i] [j-1] + arr [i-1] [j] =arr [i-1] [j-1]
-
Trả về arr [len1] [len2]
-
In kết quả.
Ví dụ
#include <iostream>
using namespace std;
// To count the number of subsequences in the string
int countsequences(string str, string str2){
int n1 = str.length();
int n2 = str2.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++){
for (int j = 0; j <= n2; j++){
dp[i][j] = 0;
}
}
// for each character of str
for (int i = 1; i <= n1; i++){
// for each character in str2
for (int j = 1; j <= n2; j++){
// if character are same in both
// the string
if (str[i - 1] == str2[j - 1]){
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
}
else{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
}
}
}
return dp[n1][n2];
}
int main(){
string str = "abcdejkil";
string str2 = "bcdfkaoenlp";
cout <<"count is: "<<countsequences(str, str2) << endl;
return 0;
} Ví dụ
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
Số lượngcount is: 51