Applying DP principles to tree and graph structures, often using DFS.
Dynamic Programming is not limited to linear sequences or 2D grids; it is a highly effective technique for problems on trees and graphs as well. 'DP on Trees' typically involves a post-order traversal (or DFS) where we compute the DP state for a node based on the already computed states of its children. For instance, to find the maximum path sum between any two nodes in a tree, for each node, we can compute the maximum length of a path starting at that node and going down into its subtrees. By combining the two longest such paths through the current node, we can update a global maximum. 'DP on Graphs' is most commonly applied to Directed Acyclic Graphs (DAGs). Since a DAG has a topological ordering and no cycles, we can define a DP state on its vertices and compute it in an order consistent with the topological sort. A classic example is finding the longest path in a DAG. We can define `dp[u]` as the length of the longest path starting at vertex `u`. This can be computed as `dp[u] = 1 + max(dp[v])` for all edges `(u, v)`. These techniques open up a new class of problems that can be solved efficiently with DP.