Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explored the idea of Dynamic Programming on Trees in depth and presented some practice problems.
Table of contents:
- Dynamic Programming on Trees
- How to identify DP on Trees?
- Practice Problems on "Dynamic Programming on Trees"
Pre-requisites:
Dynamic Programming on Trees
Dynamic Programming is the technique of utilizing the answer of smaller problem set to find the answer of a larger problem set.
DP(N1) = F(DP(M1), DP(M2), …, DP(MP))
where:
- DP(j) is the answer for a problem set of Binary Tree where root node is j
- DP denotes Dynamic Programming as a convention
- Mi and N1 are different root nodes and hence, denote different sub-trees
- M1, M2, …, MP are child nodes of node N1
- F is the function of how value of smaller sub-trees DP(Mi) are used
This is the mathematical formulation of Dynamic Programming on Trees.
Note a larger problem set that is DP(N1) is using the values of smaller problem sets that is sub-tree with child nodes to calculate the answer. The value of a smaller problem set in-turn depend on smaller problem sets and are pre-computed.
How to identify DP on Trees?
There are multiple ways to identify how Dynamic Programming can be applied on a Tree Data Structure. It is also, a challenge to formulate the problem as a Tree problem.
Some of the general techniques will be as follows:
- Minimum or Maximum values
In such cases, we need to find the maximum sum path or longest path and so on in problems. If Dynamic Programming applies to these problems, then the structure is as follows:
DP[A] = MAXIMUM(DP[B1], DP[B2], ...) + constant
where:
- DP[A] is the answer for sub-tree rooted at A
- B1, B2, ... are child nodes of node A
- DP[Bi] is the answer for a smaller sub-tree
- constant is based on node A or child nodes B1, B2, ...
Similarly, maximum can be replaced by minimum for specific problems.
- Addition of sub-tree values
In such cases, we need to find the sum of sub-problems instead of maximum/ minimum in case of previous approach. If Dynamic Programming applies to these problems, then the structure is as follows:
DP[A] = DP[B1] + DP[B2] + ... + constant
where:
- DP[A] is the answer for sub-tree rooted at A
- B1, B2, ... are child nodes of node A
- DP[Bi] is the answer for a smaller sub-tree
- constant is based on node A or child nodes B1, B2, ...
A modification to this case will be that not all smaller sub-trees are added or the weight with which each smaller sub-tree is added is different.
DP[A] = W1 * DP[B1] + W2 * DP[B2] + ... + constant
where:
- Wi >= 0
- Wi is the weight with which a smaller sub-tree Bi is added.
The exact relation and DP structure depends on the problem at hand. There can be several variants of the basic DP structure like:
- DP[i] = value of subtree rooted at node i
- DP[i][j] = value of node at index (i, j) in a matrix
- DP[i][j] in graph = value involving nodes i and j (may be number of paths from i to j)
- DP[i][j][k] in graph = value involving nodes i and j with a constraint k.
Solving graph based problems using Dynamic Programming increases your skill further as tree data structure is a restricted case of graph data structure.
Practice Problems on "Dynamic Programming on Trees"
Following are some Practice Problems where Dynamic Programming is applied on Tree based problems:
- Find height of every node of Binary Tree
- Find diameter of Binary Tree using height of every node
- Find diameter of N-ary Binary Tree
- Largest Independent Set in Binary Tree
- Binary Lifting with kth ancestor
- Minimum number of nodes to be deleted so that at most k leaves are left
Following are some Practice Problems where Dynamic Programming on Graph problem is applied:
- Find path with maximum average value in a 2D matrix
- Minimum Cost Path in 2D matrix
- Maximum Cost Path in 2D matrix
- Maximum average value path in a 2D matrix (Restricted)
- Minimum average value path in a 2D matrix (Restricted)
- Count paths from Top Left to Bottom Right of a Matrix
- Minimum Cost for Triangulation of a Convex Polygon
- Number of paths with k edges
- Shortest Path with k edges
- Vertex Cover Problem
