**DP Bitmask(Quy hoạch động trạng thái)**
-Định nghĩa:
Là một kiểu quy hoạch động mà thường dùng khi mỗi thành phần chỉ có 2 trạng thái là có/không.Khi này,ta sẽ duyệt qua tất cả các trạng thái của chúng,sau đó tối ưu từng trạng thái để sử dụng cho
những trạng thái sau đó.
VD:https://oj.vnoi.info/problem/lem3
**-Thuật toán ngây thơ:**
Ta có một cách đơn giản đó là duyệt hết mọi cách đi mà người đưa thư có thể đi.Trong quá trình duyệt,
mình sẽ kết hợp với việc tính toán chi phí của quãng đường rồi sau đó tìm được kết quả tối ưu.
Độ phức tạp sẽ là O(n!) do ta phải duyệt hết các hoán vị của n điểm
**-Sử dụng DP Bitmask:**
Gọi mask là tập các điểm ta đã đi qua.mask được biểu diễn bằng số tự nhiên có n bit,
với bit thứ i có giá trị là 0/1 tương ứng với điểm i đi hoặc chưa đi qua.
Khi này,lúc đi đến một điểm mới chính là việc ta bật một đang từ 0 của mask trở thành 1.
Gọi dp[mask][i] là giá trị tối ưu của hành trình đi qua các điểm trong tập mask,và kết thúc tại điểm i(bit thứ i của mask là 1).Ta có công thức quy hoạch động:
dp[mask][i]=Min(dp[mask^(1<<i)][j] + d[j][i]) (i,j thuộc mask,j khác i)
Giải thích công thức:
mask^(1<<i) tương ứng với trạng thái trước khi thêm i vào tập
j là điểm cuối cùng mà ta đi đến trước khi đi đến i
Kết quả của bài toán sẽ là Min(dp[(1<<n)-1][i]) với mọi i=1..n
code:https://ideone.com/AqoCpo
Độ phức tạp : O((n^2)*(2^n))