Dynamic Programming

DP on Trees

Sometimes, there are tree problems, and you need do DP on them.

Resources

• https://usaco.guide/gold/dp-trees?lang=cpp
• https://codeforces.com/blog/entry/20935

It seems intimidating at first, but when you really look at it, it’s not that hard, not much different than regular DP.

Instead of something like

dp[i] = max(A[i] + dp[i+2], dp[i+1])

You need do it on trees

dp[i] = max(A[i] + sum_grandchild[i+1], SUM child[i])

Seems like they like to use dp1 and dp2.