For Optimal BST, cost(i,j)=∑l=ijfl (sum of frequencies). I'll verify QI: cost(a,c)+cost(b,d)≤cost(a,d)+cost(b,c). Left side: ∑l=acfl+∑l=bdfl.
The middle part [b,c] is counted twice. Right side: ∑l=adfl+∑l=bcfl. The full span [a,d] plus the middle [b,c] again. Breaking into pieces: left = ∑ab−1+2∑bc+∑c+1d. Right = same expression. They're equal! Since left = right, we have left ≤ right. QI holds.