Additional DP Optimizations and Techniques

Knuth's Optimization

Tutorials

Knuth's optimization is a special case of Range DP. In general, it is used to solve DP problems with transitions of the form

Further, the cost function must satisfy the following conditions for all $a\leq b\leq c \leq d$:

1. $\texttt{cost}[b][c] \leq \texttt{cost}[a][d]$
2. $\texttt{cost}[a][c] + \texttt{cost}[b][d] \leq \texttt{cost}[a][d] + \texttt{cost}[b][c]$ (the quadrangle inequality)

Define $\texttt{opt}[i][j]$ be the index for which $\texttt{dp}[i][k] + \texttt{dp}[k+1][j]$ takes on its minimum value, or equivalently,

If more than one such index exists, then take the minimum (or the maximum, doesn't matter). Then, assuming conditions on the dp transition and the cost function to be satisfied, we can show that $\texttt{opt}$ satisfies

The proof of correctness for this claim is in the resources above.

The structure of the code is identical to that of Range DP, with the exception of maintaining the $\texttt{opt}$ array. To calculate $\texttt{dp}[i][j]$ and $\texttt{opt}[i][j]$, it is only necessary to check values of $k$ between $\texttt{opt}[i][j-1]$ and $\texttt{opt}[i+1][j]$. Because of the monotonicity of $\texttt{opt}$, the time complexity of the final algorithm can be shown to be $\mathcal{O}(N^2)$.

Knuth's Optimization Problems

Connected-Component DP

Connected-Component DP Problems