ĐỀ BÀI:
- Trích dẫn :
Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.
Input
Dòng 1: chứa xâu A
Dòng 2: chứa xâu B
Output
Chỉ gồm một dòng ghi độ dài xâu C tìm được
Example
Input:
abc1def2ghi3
abcdefghi123
Output:
10
THUẬT TOÁN:
+ Tạo 1 mảng 2 chiều p[i][j] để đếm các kí tự trùng nhau, i trong dãy A, j trong dãy B
+ Nếu i=0 hoặc j=0 sẽ không có dãy con chung nào
+ Nếu Ai = Bj đếm p[i][j] lên 1 đơn vị
+ Nếu không giá trị tại p[i][j] đó sẽ bằng MAX của dòng trên hoặc cột bên trái (mục đích để tạo gốc để tiếp tục đếm p[i][j] lên) (mấy anh giải thích kĩ chỗ này hộ em với)
+ Xuất p[i][j] lớn nhất
[You must be registered and logged in to see this image.]trong hình trên muốn đếm lên 4 hay 7 phải có 3 hoặc 6..
SOURCE CODE:
- Code:
-
import java.util.Scanner;
class Test_2_UseDynamicPrograming_QuyHoachDong
{
public static void main(String[] args)
{
Scanner nhap = new Scanner(System.in);
String a = nhap.nextLine();
String b = nhap.nextLine();
int u=0;
char c1[] = a.toCharArray();
char c2[] = b.toCharArray();
int[][] p = new int[400][400];
int c1Len = c1.length +1;
int c2Len = c2.length +1;
for(int i=1;i<c1Len;i++)
p[i][0] = 0;
for(int i=1;i<c2Len;i++)
p[0][i] = 0;
for(int i=1;i<c1Len;i++) {
for(int j=1;j<c2Len;j++) {
if(c1[i-1] == c2[j-1]) {
p[i][j] = p[i-1][j-1] + 1;
}else{
p[i][j] = Math.max(p[i-1][j],p[i][j-1]);
}
}
}
for(int i=0;i<c1Len;i++) {
for(int j=0;j<c2Len;j++) {
if(p[i][j]>u)
u=p[i][j];
}
}
System.out.print(u);
}
}
Mấy anh góp ý cho em với nha.
Wed Dec 07, 2011 12:16 pm by 
Tiêu đề: QBSTR - 4.34s - Dynamic programing 
Đây là solution đầu tiên của các bạn DHTH6, tiếp tục phát huy 
(bài NKPALIN tương tự ý)
