DAG DP · Longest Path · Nhóm: Quy hoạch động
Tìm đường đi dài nhất (số cạnh) trên đồ thị có hướng không chu trình bằng quy hoạch động theo thứ tự tô-pô.
Sắp các đỉnh theo thứ tự tô-pô để khi xử lý đỉnh u thì mọi đỉnh tới u đã xong.
Duyệt từng đỉnh u theo thứ tự đó, xét mỗi cạnh u→v đi ra.
Nới lỏng: dp[v] = max(dp[v], dp[u] + 1); đáp số là dp lớn nhất.
Trên DAG, thứ tự tô-pô bảo đảm không quay lại, nên đường đi dài nhất tính được đúng và nhanh trong một lượt, khác với đồ thị có chu trình vốn khó.
def longest_path(order, adj):
dp = [0] * n
for u in order:
for v in adj[u]:
if dp[u] + 1 > dp[v]:
dp[v] = dp[u] + 1
return max(dp)
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.