×

Search anything:

Dynamic Programming on Trees

Free book on Graph Algorithms

Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored the idea of Dynamic Programming on Trees in depth and presented some practice problems.

Table of contents:

  1. Dynamic Programming on Trees
  2. How to identify DP on Trees?
  3. 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:

Following are some Practice Problems where Dynamic Programming on Graph problem is applied:

Dynamic Programming on Trees
Share this