Dynamic Programming
01 / The shared mechanism
A table fills itself, one cell at a time — each entry composed from a constant number of earlier ones. The recurrence changes per sub-pattern, but the machinery — state, transition, fill order — is shared.
02 / The one-sentence essence
Run a post-order DFS — resolve both children before the parent. Each node returns a pair of values: the best you can collect if you rob this node, and the best if you skip it.
Problemmax stolen without adjacent nodesTree[3, 4, 5, 1, 3, -, 1]
Post-order DP on a binary tree — each node resolves once both subtrees return their rob / skip pair.
step
0 / 7
node
—
rob
—
skip
—
answer
—
0 / 7
03 / The pattern signature
# tree DP — post-order, each node returns (rob, skip)function dp(node):if node is null: return (0, 0)(lr, ls) ← dp(node.left) # recurse left first(rr, rs) ← dp(node.right) # then rightrob ← node.val + ls + rs # take node, skip both childrenskip ← max(lr, ls) + max(rr, rs) # best from each childreturn (rob, skip)lr, ls ← dp(root)answer ← max(lr, ls)
04 / When to recognize this pattern
"post-order is mandatory"
The parent cannot decide until both children have resolved. Pre-order or in-order would force you to guess the child values. Post-order is the natural traversal order for bottom-up computation.
"return a pair, not one value"
A single scalar per node isn't enough — the parent needs to know both outcomes (rob and skip) before it can make its own decision. Returning a pair is the minimal interface between a subtree and its parent.
"null base case (0, 0)"
A null child contributes 0 to both rob and skip. This makes the recurrence uniform — no special-casing for leaves or one-child nodes in the loop body. The base case propagates cleanly.
"generalises beyond rob/skip"
Any problem where a node's optimal value depends on its children's optimal values follows this shape: post-order DFS, return a small fixed tuple, combine at the parent. Diameter (longest path through root vs. not), maximum path sum, and tree cameras are all the same skeleton.
05 / Common pitfalls
Using a hash map or global memo instead of return values.
A common mistake: define
dp as a hash map from node to value, then fill it from a top-down recursive call with memoization. This works but hides the bottom-up structure. The return-value approach is strictly cleaner — it makes the data flow explicit and uses O(H) stack space instead of O(N) memo space.Only returning the final answer instead of the full pair.
If you write
dp(node) = max(rob, skip) and return a single number, the parent can't distinguish between the two. It ends up with incorrect transitions — e.g. it might assume a child's answer is always a "skip" and over-count. Always return the full pair until the very root.Confusing which value to use when combining children.
rob(node) = val + skip(left) + skip(right) — you add the children's skip values, not their rob values, because robbing the parent forbids robbing the children. skip(node) = max(rob(L), skip(L)) + max(rob(R), skip(R)) — each child independently chooses its best. Swapping these two recurrences is a common mistake that leads to wrong answers.06 / Go practice — on LeetCode
medium16
01Unique Binary Search Trees II— LC 95→02Unique Binary Search Trees— LC 96→03House Robber III— LC 337→04Path Sum III— LC 437→05Longest Univalue Path— LC 687→06All Possible Full Binary Trees— LC 894→07Distribute Coins in Binary Tree— LC 979→08Smallest String Starting From Leaf— LC 988→09Tree Diameter— LC 1245→10Maximum Product of Splitted Binary Tree— LC 1339→11Longest ZigZag Path in a Binary Tree— LC 1372→12Count Good Nodes in Binary Tree— LC 1448→13Diameter of N-Ary Tree— LC 1522→14Number of Good Leaf Nodes Pairs— LC 1530→15Most Profitable Path in a Tree— LC 2467→16Minimum Score of a Path Between Two Cities— LC 2492→
hard7
01Binary Tree Maximum Path Sum— LC 124→02Sum of Distances in Tree— LC 834→03Binary Tree Cameras— LC 968→04Number of Ways to Reorder Array to Get Same BST— LC 1569→05Longest Path With Different Adjacent Characters— LC 2246→06Difference Between Maximum and Minimum Price Sum— LC 2538→07Count Number of Possible Root Nodes— LC 2581→
— / When to use which
1-D linear
Use when the answer at index i depends on a constant number of earlier indices.
house-robber · climbing-stairs · max-subarray
2-D grid
Use when the state has two indices — a grid, or two interacting sequences.
min-path · LCS · edit-distance
knapsack
Use when each item triggers a choose-or-skip decision under a capacity constraint.
subset-sum · coin-change · partition
interval
Use when the state is a range
(i, j) and the answer composes from inner intervals.palindrome · matrix-chain · burst-balloons
state machine
Use when each index can be in one of several finite states with rules for transitioning between them.
stock · cooldown · two-state
tree DP
Use when the problem lives on a tree and each node's answer depends on its children's answers.
house-robber-III · diameter · max-path-sum
bitmask
Use when state is a subset of items (typically
N ≤ 20) and only which items have been chosen matters — not the order.assignment · TSP · sufficient-team