Lesson 28 — Quy hoạch động trên cây

State gắn với mỗi node, tính từ lá lên gốc bằng post-order DFS. Ba module: (1) khung DFS post-order, (2) House Robber III, (3) Tree Diameter.

Module 1 — Tree DP post-order (size subtree)

Animate DFS post-order: tô node đang xử lý (vàng), gộp dp[node] = 1 + Σ dp[con] từ lá lên gốc, hoàn tất chuyển sang xanh. Đây là subtreeSize (mục 5 README).

chưa xử lý đang xử lý đã tính dp

Bấm "Chạy từng bước" để duyệt post-order. Số đỏ dưới mỗi node = dp (size subtree).

Module 2 — House Robber III (max independent set)

Mỗi node có trọng số (tiền). Tính dp[node][0] (không cướp) và dp[node][1] (cướp). Không cướp 2 node kề. Cuối cùng tô đỏ tập node được chọn tối ưu.

đang tính đã có dp[0]/dp[1] được CƯỚP

Trọng số hiện trong node. Cặp số dưới node = [dp0 | dp1].

Module 3 — Tree Diameter (đường kính)

DFS trả down(node) = nhánh sâu nhất. Tại mỗi node giữ 2 chiều cao con lớn nhất → cập nhật đường kính. Cuối cùng tô tím đường kính.

đang xử lý đã có down trên đường kính

Số đỏ dưới node = down(node) (nhánh sâu nhất, số cạnh). Đường kính tô tím.