Biến đổi sâu?

[paliauthentic]

Cho 2 sâu X,Y. ta có 3 phép biến đổi với sâu X như sau:
-chèn 1 kí tự vào X.
-thay thế một kí tự của X.
-xóa đi 1 kí tự của X.
yêu cầu: hãy dùng các phép biến đổi trên để biến sâu X thành sâu Y với ít phép biến đổi nhất.
VD:
xâu X: PBBCEFATZ
xâu Y: QABCDABEFA
cho raket611 quả là: 7

các anh các chị giúp em với?

[accxaydung]

Cho 2 sâu X,Y. ta có 3 phép biến đổi với sâu X như sau:
-chèn 1 kí tự vào X.
-thay thế một kí tự của X.
-xóa đi 1 kí tự của X.
yêu cầu: hãy dùng các phép biến đổi trên để biến sâu X thành sâu Y với ít phép biến đổi nhất.
VD:
xâu X: PBBCEFATZ
xâu Y: QABCDABEFA
cho raket611 quả là: 7

các anh các chị giúp em với?

Dùng qhd:
Gọi f(i,j) là số lượng phép ít nhất để biến đổi xâu copy(x,1,i) thành xâu copy(y,1,j). Ta có:
- X=Y[j] thìL f(i,j)=f(i-1,j-1).
- Ngược lại xét 3 phép:
+ Xóa đi X để biến copy(x,1,i-1) thành copy(y,1,j), số phép biến đổi: f(i,j)=f(i-1,j)+1.
+ Biến đổi copy(x,1,i) thành copy(y,1,j-1) rồi chèn thêm Y[j] vào, số phép biển đổi: f(i,j)=f(i,j-1)+1
+ Biến đổi copy(x,1,i-1) thành copy(y,1,j-1) rồi thay thế x thành y[j], số phép biển đổi là:
f(i,j)=f(i-1,j-1)+1.
Tóm lại:
- x=y[j]: f(i,j)=f(i-1,j-1)
- x<>y[j]: f(i,j)=min(f(i-1,j)+1,f(i,j-1)+1,f(i-1,j-1)+1).

[chongthamhp]

Em xem trong quyển ebook của thầy Lê Minh Hoàng cũng có thì phải, hoặc search cái "các bài toán quy hoạch động kinh điển", đọc qua sẽ hiểu rõ hơn công thức binhnguyen đưa ra.