DP on a DAG (Topological Order & Relaxation) — DAG மீது DP — topo வரிசை

DAG — topo வரிசை; விளிம்பு தளர்வு.

உண்மை உலகில் இது ஏன் முக்கியம்?

பாடநெறி தொடர்; build அடுக்கு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

topo; max அல்லது sum.

Pythonில் முயற்சி செய்வோம்

from collections import deque


def longest_path_on_dag(n: int, edges: list[tuple[int, int, int]]) -> int:
    indeg = [0] * n
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        indeg[v] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    dp = [0] * n
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            dp[v] = max(dp[v], dp[u] + w)
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return max(dp)


print(longest_path_on_dag(4, [(0, 1, 3), (1, 2, 2), (0, 2, 5), (2, 3, 1)]))

அடிக்கடி நேரும் தவறுகள்

• சுழற்சி.
• துண்டு கிராஃப்.

முக்கியச் சுருக்கக் குறிப்புகள்

• சுழற்சி சோதனை.
• பல மூலம்.