Skip to main content

DP on Trees & Graphs

Applying dynamic programming to tree and graph structures requires understanding how to traverse and compute optimal solutions on these data structures.

Tree DP​

  • Tree Traversal: Post-order traversal for bottom-up computation
  • State Definition: dp[node] = optimal solution for subtree rooted at node
  • State Transition: Combine solutions from child nodes
  • Base Case: Leaf nodes with known values

Graph DP​

  • Topological Order: Process nodes in topological order for DAGs
  • State Definition: dp[node] = optimal solution ending at node
  • State Transition: Consider all incoming edges
  • Cycle Handling: Use memoization for graphs with cycles

Path counting​

  • Number of Paths: Count paths from source to destination
  • Shortest Path Count: Count shortest paths between nodes
  • Unique Paths: Count paths with specific constraints
  • Path with Obstacles: Count paths avoiding certain nodes/edges

Subtree problems​

  • Maximum Subtree Sum: Find subtree with maximum sum
  • Subtree Size: Count nodes in each subtree
  • Subtree Diameter: Find longest path in each subtree
  • Subtree Validation: Check if subtree satisfies certain properties

Game theory DP​

  • Minimax: Optimal play in two-player games
  • Grundy Numbers: Sprague-Grundy theorem for impartial games
  • Nim Game: Classic game theory problem
  • Game Trees: Representing game states as tree structures