10.2.2004 Ch. 1: Dynamic Programming 1
Dynamic Programming
10.2.2004 Ch. 1: Dynamic Programming 2
Gi i thi uớ ệ
°Dynamic programming
—gi i bài toán b ng cách k t h p các l i gi i c a các bài toán con.ả ằ ế ợ ờ ả ủ
—( đây “programming” không có nghĩa là l p trình).ở ậ
°So sánh dynamic programming và “chia-và-tr ” (divide-and-conquer)ị
—Gi i thu t chia-và-trả ậ ị
°chia bài toán thành các bài toán con đc l pộ ậ ,
°gi i chúng b ng đ quy,ả ằ ệ
°k t h p chúng đ có l i gi i cho bài toán ban đu.ế ợ ể ờ ả ầ
—Gi i thu t dynamic programmingả ậ
°các bài toán con không đc l pộ ậ v i nhau: chúng có chung các ớ
bài toán con nh h n.ỏ ơ
°gi i m i bài toán con ch m t l n, và ghi nh l i gi i đó ả ỗ ỉ ộ ầ ớ ờ ả
trong m t b ng đ truy c p khi c n đn.ộ ả ể ậ ầ ế
10.2.2004 Ch. 1: Dynamic Programming 3
Bài toán t i uố ư
°Bài toán t i uố ư
—có th có nhi u l i gi iể ề ờ ả
—m i l i gi i có m t trỗ ờ ả ộ ị
°Tìm l i gi i có tr t i u (c c ti u hay c c đi).ờ ả ị ố ư ự ể ự ạ
10.2.2004 Ch. 1: Dynamic Programming 4
Nguyên t c c a dynamic programmingắ ủ
°M t gi i thu t dynamic programming đc xây d ng qua b n b c:ộ ả ậ ượ ự ố ướ
1. Xác đnh c u trúc c a m t l i gi i t i u.ị ấ ủ ộ ờ ả ố ư
2. Đnh nghĩa đ quy cho ị ệ giá trị c a m t l i gi i t i u.ủ ộ ờ ả ố ư
3. Tính giá trị c a m t l i gi i t i u t d i lên (“bottom-up”).ủ ộ ờ ả ố ư ừ ướ
4. Xây d ng ựl i gi iờ ả t i u t các thông tin đã tính.ố ư ừ
10.2.2004 Ch. 1: Dynamic Programming 5
Nhân m t chu i ma tr nộ ỗ ậ
°Cho m t chu i ma tr n ộ ỗ ậ A1, A2,..., An.
°Xác đnh tích ịA1A2 An d a trên gi i thu t xác đnh tích c a hai ma ự ả ậ ị ủ
tr n.ậ
°Bi u di n cách tính tích c a m t chu i ma tr n b ng cách “ể ễ ủ ộ ỗ ậ ằ đt gi a ặ ữ
ngo cặ” (parenthesize) các c p ma tr n s đc nhân v i nhau.ặ ậ ẽ ượ ớ
°M t tích c a m t chu i ma tr n là ộ ủ ộ ỗ ậ fully parenthesized n u nó làế
—m t ma tr n ho c làộ ậ ặ
—tích c a hai tích c a chu i ma tr n ủ ủ ỗ ậ fully parenthesized khác, và
đc đt gi a ngo c.ượ ặ ữ ặ
Ví d : m t vài tích c a chu i ma tr n đc fully parenthesized ụ ộ ủ ỗ ậ ượ
—A
—(AB)
—((AB)C).