Thought process to solve tree based Dynamic Programming problems

I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems and I was hoping somebody could please explain their thought process.

I will talk about my thought process behind array based problems and then explain my troubles with tree based DP problems.

My thought process for array problems

The way I think about DP in array based problems is as follows. Let us consider a problem like Minimum Path Sum. Here the objective is to get from the top left to bottom right positions in a matrix such that we minimize the cost of the path. We can only move left and right.

The way I would approach problems like this is as follows:

• First I would construct a recurrence. In this case the recurrence is as follows

The recurrence is:

f(i, j) = a[i][j] // if i == m and j == n
f(i, j) = a[i][j] + f(i, j+1) // if i == m
f(i, j) = a[i][j] + f(i+1, j) // if j == n
f(i, j) = a[i][j] + Math.min( f(i, j+1), f(i+1, j) ) // Otherwise

-
Next I look at the equations which tells me the problem can be solved using DP as there are overlapping subproblems in f(i+1, j) and f(i, j+1). There is also an optimal substructure.

-
I can also tell the time/space complexity just by looking at the recurrence.

• Because we must compute all states which is all (i,j) pairs and because time per state is O(1) (adding a[i][j] to result) the time complexity is O(n^2).

• Looking at the recurrence, i depends only on i+1 and not on i+2, i+3 ... similarly j depends only on j+1 and not on j+2, j+3... so we can get away with using only 1 extra row (either i+1 or j+1) instead of the entire matrix so space complexity is O(n).

Hence I would come up with a n^2 time and n space solution. I can do this without any problems.

My thought process for tree problems

However I am having a hard time applying the same thought process to tree based DP problems. As an example le

I don't know if this helps, but I also struggled a great deal with DP problems on trees, and what helped for me was considering some simpler problems first, and really do a bunch of exercises of this type. It also really helps to program them in (e.g.) Python so that you get some hands-on experience.

So, perhaps it is better to start with a simpler tree problem first, like (weighted) Vertex Cover or (weighted) Independent Set?

In both these cases (they are similar, but let us focus on Vertex Cover), the
entire solution of a subtree can be summarized in the root of the subtree with
two numbers: the optimal solution if the root of the subtree is in the vertex
cover, and the optimal solution if the root of the subtree is not in the
vertex cover (but covered from below).

So the plan is to store, for each node $u$, two numbers, $u_{\text{in}} = c_i$
and $u_{\text{in}} = c_o$, and in the end, we will look at what are the values
in the root node $r$, i.e. $r_{\text{in}}$ and $r_{\text{out}}$.

The Algorithm

The algorithm is then quite simple. For the base case, starting at the leaves, in leaf node $v$, you store $v_{\text{in}} = w(v)$ and $v_{\text{out}} = 0$. Clearly, in the subtree with only one node, there are no edges to cover, so this is quite easy.

Then the rest of the algorithm is given a node $v$ with children $u_1, \dots, u_d$, we need to compute two cases.

• $v$ is in the vertex cover: then the optimal solution is $v_{\text{in}} = w(v) + \sum_{u \in u_1 \dots u_d} \min(u_{\text{in}}, u_{\text{out}})$

• $v$ is not in the vertex cover, so all children must be, hence $v_{\text{out}} = \sum_{u \in u_1 \dots u_d} u_{\text{in}}$

Now, the only thing we need to do is return the result of the root node $r$, which can either be in or not in the vertex cover, so we return
$$ \min( r_{\text{in}}, r_{\text{out}}) $$

In other words, we found out what information we need in the "separator" of a
subtree, and how can combine the information from the subtree with the rest of
the tree.

• Exercise: Solve Weighted Vertex Cover and Weighted Independent Set on trees.

• Exercise 2: Solve Weighted Dominating Set, which needs one more state, namely in the dominating set, not in the dominating set but dominated, not yet dominated (dominated from above).

StackExchange Computer Science Q#119707, answer score: 4