tree DP

Work in Progress

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
k5k3k4k2k1

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