Chương 43 - Topological Sort kết hợp Dynamic Programming

DP trên DAG = topo sort + DP linear theo thứ tự topo. State của node phụ thuộc các node “trước” nó trong topo order.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • DP trên DAG = topo order + DP theo thứ tự.
  • Longest path / closure / counting paths - 3 mẫu chính.
  • Direction: cạnh u → v nghĩa là u xong trước v.
  • Bài thường: Course Schedule IV (reachability), Largest Color Value (DP per color).

Khi nào dùng pattern này?

  • DAG với dependency rõ ràng.
  • Tính shortest/longest path trên DAG.
  • Tổ hợp DP + topological.

Bài tự luyện cuối chương

  • LC 1462 - Course Schedule IV
  • LC 2192 - All Ancestors of a Node

43.1 Longest Increasing Path in a Matrix (LC 329)

Đề bài

Ma trận. Tìm longest path tăng dần (4 hướng).

Ví dụ 

Input:  matrix = [[9, 9, 4],
                  [6, 6, 8],
                  [2, 1, 1]]   (grid m × n, đi 4 hướng, value phải TĂNG nghiêm ngặt)
Output: 4   (path tăng dài nhất: 1 → 2 → 6 → 9)

Ràng buộc

  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31-1

Clarifying questions

  • Matrix 1×1? → Trả 1.
  • Path strict increasing? → Có (> không ≥).

Hướng tiếp cận

DAG ngầm: mỗi ô là 1 node, cạnh u → v nếu mat[v] > mat[u]. DFS với memo.

Code Python 3 

from functools import cache
from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]

        @cache
        def dfs(r: int, c: int) -> int:
            best = 1
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            return best

        return max(dfs(r, c) for r in range(rows) for c in range(cols))

Phân tích độ phức tạp

  • Thời gian: O(R · C).
  • Bộ nhớ: O(R · C) cho memo.

Bình luận

  • Bẫy: memoize key là (r, c); không cần tracking visited (DAG implicit).
  • Follow-up: LC 2328 (Number of Increasing Paths).

Bài tự luyện liên quan

  • LC 2328 - Number of Increasing Paths in a Grid
  • LC 1857 - Largest Color Value (bài 43.3)

43.2 Parallel Courses III (LC 2050)

Đề bài

Input: n (số khoá, đánh số 1..n), relations: List[List[int]] - mỗi [a, b] nghĩa phải xong khoá a trước b (cạnh DAG a → b), và time: List[int] với time[i] = thời gian học khoá i+1. Có thể học đồng thời nếu prerequisite đã xong. Min thời gian tổng.

Ví dụ 

Input:  n=3, relations=[[1,3],[2,3]], time=[3,2,5]
Output: 8

Ràng buộc

  • 1 <= n <= 5·10^4
  • 0 <= len(relations) <= min(n·(n-1)/2, 5·10^4)

Clarifying questions

  • n = 1? → Trả time[0].
  • Cycle? → Theo đề: DAG.

Hướng tiếp cận

Topo sort + DP. dp[u] = time[u] + max(dp[v] for v là prerequisite).

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        graph = defaultdict(list)
        indeg = [0] * (n + 1)
        for u, v in relations:
            graph[u].append(v)
            indeg[v] += 1

        dp = [0] * (n + 1)
        queue = deque()
        for i in range(1, n + 1):
            if indeg[i] == 0:
                dp[i] = time[i - 1]
                queue.append(i)
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                dp[v] = max(dp[v], dp[u] + time[v - 1])
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)
        return max(dp)

Phân tích độ phức tạp

  • Thời gian: O(V + E).
  • Bộ nhớ: O(V + E).

Bình luận

  • Bẫy: dp[v] = max(dp[v], dp[u] + time[v]) - đảm bảo max của tất cả prerequisite.
  • Follow-up: LC 1136 (Parallel Courses) khi mỗi khoá same time.

Bài tự luyện liên quan

  • LC 207 - Course Schedule (Chương 9.4)
  • LC 1136 - Parallel Courses (Chương 13.6)

43.3 Largest Color Value in a Directed Graph (LC 1857)

Đề bài

Input: colors: str (colors[i] = ký tự màu của node i, 'a'..'z') và edges: List[List[int]] - cạnh có hướng [u, v]. Tìm path mà max số node cùng 1 color trên path là lớn nhất.

Ví dụ 

Input:  colors="abaca", edges=[[0,1],[0,2],[2,3],[3,4]]
Output: 3

Ràng buộc

  • n == len(colors)
  • 1 <= n <= 10^5

Clarifying questions

  • Cycle? → Trả -1.
  • n = 1? → Trả 1.

Hướng tiếp cận

Topo + DP dp[u][c] = số node màu c lớn nhất đi qua u (kết thúc tại u).

dp[v][c] = max(dp[v][c], dp[u][c] + (1 if color[v] == c else 0)).

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        graph = defaultdict(list)
        indeg = [0] * n
        for u, v in edges:
            graph[u].append(v)
            indeg[v] += 1
        dp = [[0] * 26 for _ in range(n)]
        queue = deque()
        for i in range(n):
            if indeg[i] == 0:
                queue.append(i)
                dp[i][ord(colors[i]) - 97] = 1
        visited = 0
        best = 0
        while queue:
            u = queue.popleft()
            visited += 1
            best = max(best, max(dp[u]))
            for v in graph[u]:
                for c in range(26):
                    add = 1 if (ord(colors[v]) - 97) == c else 0
                    if dp[u][c] + add > dp[v][c]:
                        dp[v][c] = dp[u][c] + add
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)
        return best if visited == n else -1

Phân tích độ phức tạp

  • Thời gian: O(V · 26 + E).
  • Bộ nhớ: O(V · 26).

Bình luận

  • Cycle check: nếu visited != n → có cycle → trả -1.

Bài tự luyện liên quan

  • LC 2050 - Parallel Courses III (bài 43.2)
  • LC 1462 - Course Schedule IV (bài 43.5)

43.4 Build a Matrix With Conditions (LC 2392)

Đề bài

Cho k (size) và row/col conditions (a phải đứng trên/trước b). Trả về ma trận k×k với mỗi số 1..k xuất hiện đúng 1 lần thoả conditions.

Ví dụ 

Input:  k=3, rowConditions=[[1,2],[3,2]], colConditions=[[2,1],[3,2]]
Output: [[3,0,0],[0,0,1],[0,2,0]]

Ràng buộc

  • 2 <= k <= 400
  • 1 <= len(rowConditions), len(colConditions) <= 10^4

Clarifying questions

  • Conflicting conditions? → Trả [].
  • k = 1? → Trả [[1]].

Hướng tiếp cận

Topo sort 2 lần: row conditions → row position, col conditions → col position. Đặt mỗi số vào ô (row_pos, col_pos).

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo(conditions):
            graph = defaultdict(list)
            indeg = [0] * (k + 1)
            for u, v in conditions:
                graph[u].append(v)
                indeg[v] += 1
            queue = deque(i for i in range(1, k + 1) if indeg[i] == 0)
            order = []
            while queue:
                u = queue.popleft()
                order.append(u)
                for v in graph[u]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        queue.append(v)
            return order if len(order) == k else []

        rows = topo(rowConditions)
        cols = topo(colConditions)
        if not rows or not cols: return []
        row_pos = {x: i for i, x in enumerate(rows)}
        col_pos = {x: i for i, x in enumerate(cols)}
        result = [[0] * k for _ in range(k)]
        for x in range(1, k + 1):
            result[row_pos[x]][col_pos[x]] = x
        return result

Phân tích độ phức tạp

  • Thời gian: O(V + E).
  • Bộ nhớ: O(V + E).

Bình luận

  • Bẫy: topo sort row và column conditions độc lập - nếu một trong 2 có cycle → trả [].
  • Follow-up: LC 2392 chính bài này.

Bài tự luyện liên quan

  • LC 210 - Course Schedule II (Chương 13.1)
  • LC 269 - Alien Dictionary (Chương 13.2)

43.5 Course Schedule IV (LC 1462)

Đề bài

Cho numCourses và prerequisites[i] = [a, b] với ý nghĩa “phải hoàn thành môn a trước môn b” (tức a là prerequisite của b, cạnh DAG là a → b). Cho mảng queries[i] = [u, v]; với mỗi query, trả về True nếu u là prerequisite (trực tiếp hoặc gián tiếp) của v, tức tồn tại đường đi u → ... → v trong DAG.

Quy ước hướng cạnh (xem Chương 13): “u trước v” ⇔ cạnh u → v. Đừng đảo dấu mũi tên - đây là bug điển hình ở Course Schedule family.

Ví dụ 

Input:  numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [True, True]

Ràng buộc

  • 2 <= numCourses <= 100
  • 1 <= prerequisites.length <= n·(n-1)/2

Clarifying questions

  • Có cycle không? → Theo đề: không (DAG).
  • Reachability transitive? → Có - đó là điểm chính.

Hướng tiếp cận

Brute force: với mỗi query, BFS/DFS từ u → check v. O(Q · (V + E)).

Tối ưu - Topo + DP closure: reach[u] = set các đỉnh v mà u → ... → v. Duyệt theo topo order ngược, gán reach[u] = {u} ∪ union(reach[v] for v in adj[u]).

Sau preprocessing, mỗi query O(1).

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def checkIfPrerequisite(self, numCourses: int,
                            prerequisites: List[List[int]],
                            queries: List[List[int]]) -> List[bool]:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[a].append(b)
            indeg[b] += 1

        # Topo order.
        queue = deque(i for i in range(numCourses) if indeg[i] == 0)
        topo = []
        while queue:
            u = queue.popleft()
            topo.append(u)
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)

        # reach[u] = set các đỉnh u có thể đến.
        reach = [set() for _ in range(numCourses)]
        # Process theo topo order ngược: con đã có reach trước cha.
        for u in reversed(topo):
            for v in graph[u]:
                reach[u].add(v)
                reach[u] |= reach[v]

        return [v in reach[u] for u, v in queries]

Phân tích độ phức tạp

  • Thời gian: O(V · E + Q) (worst case set union).
  • Bộ nhớ: O(V²) cho reach sets.

Bình luận

  • Pattern “topo + DP closure” - cùng tinh thần với transitive closure (Floyd-Warshall).
  • Quy ước chiều: LC 1462 dùng prerequisites[i] = [a, b] nghĩa “a phải xong trước b” (a là prerequisite của b) ⇒ cạnh a → b trong DAG. Trùng quy ước Chương 13: “X trước Y” ⇒ X → Y.
  • Bẫy: lập trình viên hay viết graph[b].append(a) vì nhầm “b cần a” với “edge b → a”. Code đúng dưới đây là graph[a].append(b).
  • Tối ưu space: dùng bitmask thay set khi n ≤ 64.

Bài tự luyện liên quan

  • LC 207, 210 - Course Schedule (I, II).
  • LC 2192 - All Ancestors of a Node.

43.6 Find All Possible Recipes from Given Supplies (LC 2115)

Đề bài

Cho recipes (mỗi cái cần ingredients), supplies (ingredients sẵn có). Trả về recipes có thể làm.

Ví dụ 

Input:  recipes=["bread"], ingredients=[["yeast","flour"]], supplies=["yeast","flour","corn"]
Output: ["bread"]

Ràng buộc

  • n == len(recipes)
  • 1 <= n <= 100

Clarifying questions

  • recipe cần chính nó? → Trả [] cho recipe đó.
  • supplies rỗng? → Chỉ recipe không cần ingredient được.

Hướng tiếp cận

Topo sort: cạnh ingredient → recipe needs ingredient. BFS từ supplies, mỗi khi tất cả ingredients của 1 recipe đã có → recipe đó “có sẵn”.

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        graph = defaultdict(list)
        indeg = {}
        for recipe, ings in zip(recipes, ingredients):
            indeg[recipe] = len(ings)
            for ing in ings:
                graph[ing].append(recipe)

        queue = deque(supplies)
        available = set(supplies)
        result = []
        recipe_set = set(recipes)
        while queue:
            ing = queue.popleft()
            for r in graph[ing]:
                indeg[r] -= 1
                if indeg[r] == 0:
                    result.append(r)
                    available.add(r)
                    queue.append(r)
        return result

Phân tích độ phức tạp

  • Thời gian: O(V + E).
  • Bộ nhớ: O(V + E).

Bình luận

  • Bẫy: recipe có thể là ingredient của recipe khác → vẫn áp Kahn.
  • Follow-up: LC 207 (Course Schedule) - Chương 9.4.

Bài tự luyện liên quan

  • LC 207 - Course Schedule
  • LC 2192 - All Ancestors of a Node

Tóm tắt chương & Quyết định

Topo + DP taxonomy

Loại Bài tiêu biểu
Longest path on DAG LC 329 Longest Increasing Path
Counting paths LC 1976 Number of Ways to Arrive
Reachability closure Transitive closure / “có thể đạt từ A đến B”
Dependency scheduling LC 1136 Parallel Courses, LC 2050
Aggregation along DAG LC 1857 Largest Color Value

Largest Color Value (LC 1857)

  • dp[node][color] = số node màu color lớn nhất trên đường đi kết thúc tại node.
  • Topo order: với mỗi (u → v): dp[v][c] = max(dp[v][c], dp[u][c] + (1 nếu color[v] == c else 0))
    • chú ý update sau khi xét tất cả parents.
  • Nếu sau topo còn node chưa visit ⇒ có cycle ⇒ return -1.

LC 1462 - Course Schedule IV

  • “Course a là prerequisite của b?” - closure transitive.
  • Topo: với mỗi cạnh u → v, set closure[v] |= closure[u] (bitmask hoặc set).
  • Trả lời mỗi query (a, b) bằng a in closure[b].

Recipes (LC 2115)

  • Một ingredient có thể vừa là nguyên liệu thô, vừa là tên một recipe khác.
  • Build cạnh: ingredient → recipe cần nó.
  • Topo từ supply (indegree == 0 ban đầu là các ingredient có sẵn).
  • Khi tất cả ingredient của một recipe đã sẵn sàng, recipe đó được thêm vào output và bản thân nó cũng trở thành “ingredient có sẵn” cho các recipe khác.

Direction consistency (cross-reference Chương 13)

LC 1462: prerequisites[i] = [u, v] nghĩa “phải học u trước v” ⇒ cạnh u → v (giống Chương 13). Đừng đảo!