Bài giảng Cấu trúc dữ liệu và giải thuật: Quy hoạch động - TS. Đào Nam Anh

DATA STRUCTURE AND ALGORITHM<br /> Dynamic Programming<br /> <br /> CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br /> Qui hoạch động<br /> Dr. Dao Nam Anh<br /> <br /> Data Structure and Algorithm<br /> <br /> 1<br /> <br /> Resource - Reference<br /> Slides adapted from James B D Joshi,<br /> edit by Dao Nam Anh.<br /> Major Reference:<br /> <br /> •<br /> <br /> Robert Sedgewick, and Kevin Wayne,<br /> “Algorithms” Princeton University, 2011, Addison<br /> Wesley<br /> <br /> •<br /> <br /> Algorithm in C (Parts 1-5 Bundle)- Third Edition<br /> by Robert Sedgewick, Addison-Wesley<br /> <br /> •<br /> •<br /> <br /> Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.<br /> Giải thuật và lập trình, Lê Minh Hoàng, Đại Học<br /> Sư Phạm, 2002<br /> Data Structure and Algorithm<br /> <br /> 2<br /> <br /> Divide and Conquer<br /> Chia và Trị<br /> <br /> •<br /> <br /> Một số chương trình đệ qui gọi chính nó cho hai<br /> tập dữ liệu có kích thước ½<br />  Chia vấn đề này thành 2 phần và thực hiện từng<br /> phần<br /> <br /> •<br /> •<br /> <br /> Chi phí thời gian: TN = Tk + TN-k + 1<br /> <br /> Many recursive programs use recursive calls on two subsets of inputs<br /> (two halves usually)<br />  Divide the problem and solve them – divide and conquer paradigm<br />  Complexity: TN = Tk + TN-k + 1<br /> <br /> Data Structure and Algorithm<br /> <br /> 3<br /> <br /> Find max- Divide and Conquer<br /> Tìm số lớn nhất – theo cách chia và trị<br /> 2 317<br /> <br /> Item max(Item a[], int l, int r)<br /> { Item u, v;<br /> int m = (l+r)/2;<br /> if (l == r) return a[l];<br /> u = max(a, l, m);<br /> v = max(a, m+1, r);<br /> if (u > v) return u;<br /> else return v;<br /> }<br /> <br /> Data Structure and Algorithm<br /> <br /> 4<br /> <br /> Find max- Divide and Conquer<br /> Tìm số lớn nhất – theo cách chia và trị<br /> 1<br /> <br /> 2 317<br /> 2<br /> <br /> 2 3<br /> <br /> 1 7<br /> <br /> Item max(Item a[], int l, int r)<br /> { Item u, v;<br /> int m = (l+r)/2;<br /> if (l == r) return a[l];<br /> u = max(a, l, m);<br /> v = max(a, m+1, r);<br /> if (u > v) return u;<br /> else return v;<br /> }<br /> <br /> Data Structure and Algorithm<br /> <br /> 5<br /> <br />