KA xin giới thiệu 1 kĩ thuật trong lập trình ,đó là Qui hoạch động(QHD) hay còn gọi là qui hoạch tuýên tính.
Định nghĩa :QHD là phương pháp giải quyết một bài toán bằng cách qui về những bài toán con và giải quyết tất cả những bài toán con để tìm ra đáp án tối ưu.
Một ví dụ đơn giản:Cho 1 số tự nhiên n,hãy tính số cách có thể phân tích n thành tổng của các số nguyên dương bé hơn n.
Giải:Ta có thể dùnh phương pháp vét cạn để tìm tất cả các trướng hợp.Nhưng vì yêu cầu bài toán chỉ là tìm số cách phân tích nên vét cạn sẽ là 1 sự lãng phí đáng kể.
QHD:_gọi F[i,j] là số cách phân tích số j>0 thành tổng của các số nguyên dương <=i.
Xét 2 khả năng:
+ Nếu ta chọn số i vào cách phân tích,khi đó F[i,j]=F[i,j-i];
+ Nếu ta không chon i thì phép phân tích xem như chỉ chọn các số từ i-1 trở về 1,do đó F[i,j]=F[i-1,j];
Vì vậy,bài toán này sẽ có giải thuật như sau:
Cho i chạy từ 1 tới n
Cho j chạy từ 1 tới n
Nếu j<i thì gán F[i,j]=F[i-1,j]
Nếu >=i thì F[i,j]=F[i-1,j]+F[i,j-1]
Đáp số bài toán là F[n,n].Ta có thể làm tốt bài làm bằng cách sử dụng mảng 1 chiều thay vì mảng 2 chiều nhưng ở đây KA chỉ giới thiệu cách này cho dễ hiểu.
