Belajar Algoritm - DP on Trees & Graphs

#Pendahuluan

Setelah di episode 16 kita membahas DP on strings, pada episode ini kita menutup FASE 4: GREEDY & DYNAMIC PROGRAMMING dengan DP on Trees & Graphs — state DP pada struktur data yang bukan linear array. Trees dan graphs memperkenalkan tantangan baru: struktur hierarkis atau siklik yang mengubah cara kita mendefinisikan dan mengevaluasi state.

DP on trees menggunakan DFS rekursif; DP on graphs menggunakan topological sort untuk memastikan urutan evaluasi yang benar. Keduanya menunjukkan bahwa DP bukan hanya untuk array — ia adalah paradigma umum yang berlaku pada struktur data apapun.

#Diameter of Binary Tree

Diameter: panjang jalur terpanjang antara dua node mana pun. Jalur tidak harus melewati root.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def diameter_of_binary_tree(root):
    diameter = 0
    
    def depth(node):
        nonlocal diameter
        if not node:
            return 0
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        # Diameter melalui node ini
        diameter = max(diameter, left_depth + right_depth)
        return max(left_depth, right_depth) + 1
    
    depth(root)
    return diameter

DP insight: depth(node) adalah state — panjang jalur terpanjang dari node ke leaf. Diameter dihitung sebagai left_depth + right_depth di setiap node, bukan sebagai state tersendiri.

#House Robber III

House Robber III: node tree merepresentasikan rumah; kalian bisa merampok rumah tidak bersebelahan (parent dan child tidak boleh dirampok bersamaan). Maksimalkan total rampokan.

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (rob_this, skip_this)
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        # Rampok node ini: tidak bisa rampok children
        rob_this = node.val + left[1] + right[1]
        # Skip node ini: ambil max dari children
        skip_this = max(left) + max(right)
        
        return (rob_this, skip_this)
    
    return max(dfs(root))

State: tuple (rob_this, skip_this) untuk setiap node. Transition: rob_this = val + left_skip + right_skip, skip_this = max(left) + max(right).

#Shortest Path di DAG (Topological Sort + Relaxation)

Shortest path di DAG bisa diselesaikan dalam O(V + E) — lebih cepat dari Dijkstra karena tidak ada siklik → tidak perlu priority queue.

from collections import deque
 
def shortest_path_dag(graph, source, n):
    """graph: adjacency list [(to, weight)]"""
    # Step 1: Topological sort
    in_degree = [0] * n
    for u in range(n):
        for v, w in graph[u]:
            in_degree[v] += 1
    
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    topo_order = []
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v, w in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # Step 2: Relax edges in topological order
    dist = [float('inf')] * n
    dist[source] = 0
    for u in topo_order:
        if dist[u] != float('inf'):
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    
    return dist

DP insight: dist[v] = shortest path dari source ke v. Evaluasi dalam topological order memastikan semua predecessor sudah diselesaikan sebelum v → satu pass cukup.

#Matrix Chain Multiplication (Interval DP)

Matrix Chain Multiplication: diberikan rantai matrix, tentukan urutan perkalian yang meminimalkan jumlah perkalian skalar. Ini adalah contoh interval DP.

def matrix_chain(p):
    """p = [d0, d1, d2, ..., dn] di mana matrix i berukuran d[i] x d[i+1]"""
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    
    # length = panjang rantai yang dipecah
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

State: dp[i][j] = minimum cost untuk mengalikan matrix i sampai j. Transition: coba semua posisi split k, cost = dp[i][k] + dp[k+1][j] + p[i] × p[k+1] × p[j+1].

Iterasi berdasarkan length (bukan i): karena dp[i][j] bergantung pada sub-interval yang lebih pendek.

#Ringkasan DP on Trees & Graphs

#Penutup

Pada episode 17 ini, kalian telah memahami:

• DP on trees: DFS rekursif, state diwariskan dari children ke parent.
• Diameter: depth(node) + hitung max left+right di setiap node.
• House Robber III: state (rob, skip) per node.
• Shortest path DAG: topological sort + satu pass relaxation — O(V+E).
• Matrix chain: interval DP, iterate by length, coba semua split k.

Ini menutup FASE 4: GREEDY & DYNAMIC PROGRAMMING. Di episode 18 selanjutnya kita masuk ke FASE 5: GRAPH ALGORITHMS — BFS & DFS lanjut: bipartiteness check, Tarjan's SCC, articulation points, dan bridges. Sampai jumpa di episode 18!