Since the size of the set {z j |j > k} is |S| − k, hence there are at least |S| − k parse trees whose scores ϕ(z j ) are less than ψ(p, z k ).
because ϕ(z ′ ) ≥ ψ(p, z k ), hence z ′ is at least the k th best parse tree in subset S. we can search the k best parse trees in this way: for each sub-problem, we use DP to derive the k best parse trees.