Recurrence formula for optimal binary search tree This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}&lt;k_{2} &lt;\dots&lt;k_{n} $.
For each key $k_{i}$, where $1\leq i \leq n$, we have a probability $p_{i}$ that a search will be for $k_{i}$.
We let the sequence $d =\{ d_{0},d_{1},\dots,d_{n} \}$, where $d_{0}&lt;d_{1} &lt;\dots&lt;d_{n} $, be for values not in $k$.
For each key $d_{i}$, where $0\leq i \leq n$, we have a probability $q_{i}$ that a search will be for $d_{i}$.
The goal is to construct an optimal binary search tree.
Let us define $e[i,j]$ as the expected cost of searching an optimal binary search tree containing the keys $k_{i},\dots,k_{j}$.
Let $w(i,j) = \sum_{l=i}^{j} p_{l} + \sum_{l=i-1}^{j} q_{l}$.
The book gives the following equation as the recurrence formula for forming the optimal binary search tree:
$$
e[i,j] = \begin{cases}
q_{i-1} &amp; \text{if } j = i-1, \\
\displaystyle\min_{i\le r\le j} \{e[i,r-1]+r[r+1],j]+w(i,j)\} &amp; \text{if } i \leq j.
\end{cases}
$$
This formula makes sense for $i\leq j$, but I don't understand the case $j = i-1$.

Why is $e[i,i-1] = q_{i-1}$?
Quoting Introduction to Algorithms:

The easy case occurs when $j = i-1$. Then we have just the dummy key $d_{i-1}$.
The expected search cost is $e[i,i-1] = q_{i-1}$.

In slightly more detail, $e[i,j]$ is supposed to be the cost of the optimal binary search tree for $k_i,\ldots,k_j$. It is important to understand what cost means here. The cost is with respect to the following distribution on the input:

With probability $p_i$, key $k_i$ is being searched.
With probability $q_i$, a dummy key $d_i$ between $k_i$ and $k_{i+1}$. (When $i = 0$, it is a key smaller than $k_1$, and when $i = n$, it is a key larger than $k_n$.)

Unfortunately, the textbook is being extremely sloppy, and never bothers to explain what they mean by &quot;the cost of the optimal binary search tree for $k_i,\ldots,k_j$&quot;. It seems that they are measuring the expected cost with respect to the stated keys as well as with respect to the dummy keys $d_{i-1},\ldots,d_j$. That is, they want to minimize
$$
q_{i-1} \mathit{cost}(d_{i-1}) + p_i \mathit{cost}(k_i) + q_{i+1} \mathit{cost}(d_{i+1}) + \cdots + q_{j-1} \mathit{cost}(d_{j-1}) + p_j \mathit{cost}(k_j) + q_j \mathit{cost}(d_j).
$$
When $j = i-1$, there are no real keys, but there is a dummy key $d_{i-1} = d_j$, and so the cost is $q_{i-1} \mathit{cost}(d_{i-1})$. The optimal cost here is clearly $1$, and that's how they get $q_{i-1}$.