Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm I am developing a Dynamic Programming algorithm for a problem in scheduling. In the recursive formula, I have three cases: (1) $t_{i-1} = int$ (2) $t_{i-1}  = app \quad \&amp; \quad r(j) \leq p $ and (3) $t_{i-1} = app \quad \&amp; \quad r(j) &gt; p$. However, for two of them I can go to two directions. 

To explain more, suppose I have job $−1$ scheduled. Then, if $_{−1}=$, I can schedule the next job (job $$) with two conditions: (1): start it immediately after job $−1$ is finished, i.e. at point $_{−1}$ or (2): start it two time slots earlier than job $−1$ is finished, i.e. at $_{−1}−2$. Both directions should be checked in the DP.

The formula is shown in the following, that is simplified to avoid misleading. In fact, cases 1 and 2 are the same, but can go into two directions ''app'' and ''int''. The same is for cases 3 and 4. But case 5 has only one option that is ''app''. I think the current format of the formula is missing something since the condition for cases 1 and 2, and for cases 3 and 4, is the same. What is the correct form of interpreting this formula?

\begin{equation}
z_i = \begin{cases}
z_{i-1} + p + (app) &amp; \text{if $t_{i-1} = int$}\\
z_{i-1} + p+ (int) &amp; \text{if $t_{i-1} = int$}\\
z_{i-1} + 2p + (app) &amp; \text{if $t_{i-1} = app$} \quad \&amp; \quad r(j) \leqslant p\\
z_{i-1} + 2p + (int) &amp; \text{if $t_{i-1} = app$} \quad \&amp; \quad r(j) \leqslant p\\
z_{i-1} + r(j) + (app) &amp;\text{if $t_{i-1} = app$} \quad \&amp; \quad r(j) &gt; p \\
\end{cases}
\end{equation}

One thing that comes to my mind is to write it with two $\min$ functions. Since from the three conditions with $(app)$ (i.e. conditions 1, 3 and 5) one with lower objective function will be remained, and the same for the two with $(int)$ option (i.e. conditions 2 and 4). How about writing with two $\min$ functions with distinct condition for each?! For example:
\begin{equation}
z_i = \begin{cases}
\min\begin{cases} z_{i-1} + p + (app) &amp; \text{if $t_{i-1} = int$} \\ z_{i-1} + 2p + (app) &amp; \text{if $t_{i-1} = app$} \quad \&amp; \quad r(j) \leqslant p \\ z_{i-1} + r(j) + (app) &amp;\text{if $t_{i-1} = app$} \quad \&amp; \quad r(j) &gt; p\end{cases} \\
\min\begin{cases}z_{i-1} + p+ (int) &amp; \text{if $t_{i-1} = int$} \\
z_{i-1} + 2p + (int) &amp; \text{if $t_{i-1} = app$} \quad \&amp; \quad r(j) \leqslant p \end{cases}\\
\end{cases}
\end{equation}
If you want to have two values for each stage, one for $t_{i - 1} = app$ and one for $t_{i - 1} = int$, which are derived from three or two cases respectivelly then you will need to store two dynamic programming values for each stage. Let's name these values for the $i$-th stage $z_{app, i}$ and $z_{int, i}$ respectively. $z_{app, i}$ is the minimum additive value of your objective function for stages up to the $i$-th one if you used (app) in the $i$-th stage, while $z_{int, i}$ has a similar definition. Now let's see what the format of the dp recursion will look like:

$
z_{app, i} = min
\begin{cases}
z_{int, i - 1} + p + (app), &amp; \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p + (app), &amp; \text{if } t_{i - 1} = app \wedge r(j) \leq p\\
z_{app, i - 1} + r(j) + (app), &amp; \text{if } t_{i - 1} = app \wedge r(j) &gt; p
\end{cases}
$

$
z_{int, i} = min
\begin{cases}
z_{int, i - 1} + p + (int), &amp; \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p + (int), &amp; \text{if } t_{i - 1} = app \wedge r(j) \leq p
\end{cases}
$

Note that that $t_{i - 1} = int$ dictates the use of $z_{int, i - 1}$ which is the optimal value of the previous stage when (int) was used. The case when $t_{i - 1} = app$ is faced similarly by using $z_{app, i - 1}$. We have represented the optimal values of each stage using mutual recursion. Equivalently you can use the following recursion:

$
z_{app, i} = (app) + min
\begin{cases}
z_{int, i - 1} + p, &amp; \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p, &amp; \text{if } t_{i - 1} = app \wedge r(j) \leq p\\
z_{app, i - 1} + r(j), &amp; \text{if } t_{i - 1} = app \wedge r(j) &gt; p
\end{cases}
$

$
z_{int, i} = (int) + min
\begin{cases}
z_{int, i - 1} + p, &amp; \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p, &amp; \text{if } t_{i - 1} = app \wedge r(j) \leq p
\end{cases}
$

This way the dynamic programming calculations will speed up by a constant factor.