tree DP
Concept
Largest Independent Set in Trees
I(v) = size of largest independent set of the subtree rooted at v
base cases
fo leaf l, I(l) = 1
option 1
v in largest independent set
if v is included, then its children cannot, we must sum the grandchildren
val_1 = 1 +
option 2
v not in largest independent set
if v is not included, then we can sum the children
val_2 =
combine
I(v) = max{val_1, val_2}
Time complexity
Optimal Binary Search Tree
Problem
- input:
keys with frequencies - output: BST
that minimizes
Example
Greedy approach
- doesn’t work
C(i, j) = objective value of the best BST for keys
base case
C(i, i) = f_i
combine
pick a vertex l to be the root
Bottom-up
increasing order of j-i
Time complexity