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)

DP_ part 3

II.3.LCS dãy con chung dài nhất

Ta xét bài toán sau:
Cho 2 xâu, tìm xâu con chung dài nhất của chúng.  độ dài của mỗi xâu <= 1000

LIS_chặt nhị phân

Bonus: Bài toán LIS sử dụng chặt 
nhị phân 

Bài toán : Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N]. 
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn 
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử? 
Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 30000).
• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

DP_part 2

Phần II: Các bài toán và áp dụng.

Quy hoạch động thường được chia làm 2 phần:

          + Trả lời:

-         Khởi tạo.

-         Tính toán dựa theo công thức truy hồi.

          + Truy vết: in ra cấu hình tối ưu.

II.1: LIS _ Khởi đầu của DP

1.     Bài toán tổng quát.

LIS là từ viết tắt của Longest Increasing Subsequence LIS (dãy con tăng dài nhất ). Bài toán được phát biểu tổng quát như sau:

DP_part1

DP_quy hoạch động

Lời mở đầu

Đây là blog đầu tiên của tôi nên không tránh khỏi sai sót, mong bạn đọc thông cảm và góp ý với

mình ạ. ^^

Tin học mới xuất hiện, nhưng tầm ảnh hưởng của nó là vô cùng lớn. Thời đại nay, đâu đâu cũng thấy tin học, từ những chiếc máy tính để bàn, đến các công cụ, các phần mềm lập trình như C, C++ , Pascal, Python, VC , ... , hay lớn hơn nữa chính là mạng xã hội :facebook, twitter ,instagram,.. Trong bài viết này mình sẽ đề cập đến 1 vấn đề như hạt cát nhưng mang tính nền móng của tin