DP_part 4

II.4. Bài toán biến đổi xâu

Bài toán: Cho 2 xâu A, B. Ta muốn biến xâu A --> B sau 1 số thao tác và mất một vài chi phí như sau

( lưu ý các phép biến đổi đều chỉ diễn ra trên xâu A) 

+ insert(i,c) -- Chèn vào sau vị trí i , chữ cái c. với chi phí x 

+ replace(i,c) -- thay thế chữ cái thứ i bằng chữ cái c với chi phí y

+ delete(i) xóa chữ cái thứ i với chi phí z

--> in ra chi phí nhỏ nhất.

input:  Nhâp x, y, z và 2 xầu A, B( lenA , lenB <= 1000)

output:  In ra chi phí nhỏ nhất (output đảm bảo <= 10^9)

Giải:

    +Với ý tưởng gần giống như bài toán LCS. ta sẽ quy hoạch động F[i][j] - Chi phí nhỏ nhất khi biến đổi i phần tử đầu tiên của A --> j phần tử đầu tiên của B.

 Ta xét các trường hợp:

+ Nếu replace (i, b[j] ) --> F[i][j] = F[i-1][j]  + y

+ Nếu insert (b[j] ) --> F[i][j] = F[i][j-1] + x;

+ Nếu xóa phần tử thứ i --> F[i][j] = F[i-1][j] + z

+ nếu a[i] = b[j] --> F[i][j] = F[i-1][j-1];

Tóm lại : 

F[i][j] = max (F[i][j-1] + x, F[i-1][j] + z, F[i-1][j]  + y) 

TH đặc biệt a[i] = b[j] --> F[i][j] = max (F[i][j], F[i-1][j-1] 

--> nhưng hướng suy luân quy hoạch động trở nên ngày càng rõ ràng

Khởi tạo : F[0][0] = 0., F[0][i] = x*i, F[j][0] = z*j..