Chương 7 "Thuật toán quy hoạch động và áp dụng" cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung sau: Các bài toán con chung lồng nhau và giải thuật quy hoạch động, giải thuật quy hoạch động giải bài toán cái túi, giải thuật quy hoạch động giải bài toán dãy con lớn nhất, giải thuật quy hoạch động giải bài toán dãy con chung dài nhất,. | 1 1. 2. 3. 4. 5. Các bài toán con chung lồng nhau và giải thuật quy hoạch động Giải thuật quy hoạch động giải bài toán cái túi Giải thuật quy hoạch động giải bài toán dãy con lớn nhất Giải thuật quy hoạch động giải bài toán dãy con chung dài nhất. Giải thuật quy hoạch động giải nhân dãy ma trận. 2 Ví dụ về bài toán con chung lồng nhau Quy hoạch động là gì? Ba giai đoạn của bài toán quy hoạch động 3 Khi chia bài toán thành các bài toán con, trong nhiều trường hợp, các bài toán con khác nhau lại chứa các bài toán con hoàn toàn giống nhau. Ta nói rằng chúng chứa các bài toán con chung giống nhau Ví dụ: 4 Định nghĩa số Fibonaci F(n): F(0)=0 F(1)=1 F(n)=F(n-2)+F(n-1) với n>1 Ví dụ: F(2)=1, F(3)= 2, F(4) = 3 , F(5)=5, .