[Q] Hỏi về quy hoạch động

[lonestar]

Tui không rành lắm về thuật toán quy hoạch động
Ai biết có thể nói giùm tôi được không ?
Nói về thuật toán , ý nghĩa , ví dụ

[n2v82]

Quy hoạch động nhằm mục đích tìm được kết quả tối ưu. Quy hoạch động tương tự như quy nạp toán học. Quy hoạch động thực chất là phân bài toán lớn thành những bài toán nhỏ, công việc phải làm là giải những bài toán nhỏ để thu được lời giải cho bài toán tổng quát. Quy hoạch động chỉ giải quyết được những bài toán mà khi chia nhỏ có thể lưu trữ được kết quả bằng mảng.
Ví dụ : Cho hai xâu x và xâu y tìm xâu con chung dài nhất của hai xâu.

dễ thấy : f(i,j)=Max( f[i,j-1],f[i-1,j]),f[i-1,j-1]+chung(i,j))
với f(i,j) : số lượng phần tử chung lớn nhất của hai xâu x và y
chung(i,j)=1 nếu x[i]=y[j] và bằng o trong trường hợp ngược lại