-
- With[i] = wi + Without[i-1].
- Without[i] = max { With[i – 1], Without[i-1] }.
- We can prove that there is an optimal solution in which N contacts its children ci in order of decreasing R(ci). Assume without loss of generality that the children of N have been renumbered so R(c1) ≥ R(c2) ≥ … ≥ R(ck).
Then R(N) = maxi=1 to k { i + R(ci) } with R(N) = 0 if N is a leaf.
- TQ(i) = max1 ≤ j ≤ i { TQ(j-1) + Q(yj, yj+1, …, yi } if i ≥ 1, with TQ(0) = 0