Lagmental Vicfred

Interval DP Chooses the Last Split inside a Segment by Vicfred

Last updated: Thu 30 July 2015

tags: mathematics, dynamic programming, semirings, state spaces

When subproblems are contiguous intervals, the final operation separates the interval at one split point. A small computation will anchor the general statement before the abstraction takes over.

Notation

A full dynamic-programming state \(dp[i][s]\) states exactly which prefix \(i\) and mathematical state \(s\) have been processed. The recurrence is a theorem about transitions between these states.

$$ dp[l][r]=\text{optimal value for the complete interval }[l,r] $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ dp[l][r]=\min_{l\le k<r}\{dp[l][k]+dp[k+1][r]+C(l,r)\} $$

Stress the formula

This is the algebraic core of the note. Once this line is correct, the surrounding interpretation has something solid to refer to.

$$ \begin{array}{c|c|c}[l,k]&k\mid k+1&[k+1,r]\\\hline dp[l][k]&+\,C(l,r)&dp[k+1][r]\end{array} $$

Interpretation

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad dp[l][r]=\text{optimal value for the complete interval }[l,r],\\[5pt] \mathsf{C}\;&:\quad dp[l][r]=\min_{l\le k<r}\{dp[l][k]+dp[k+1][r]+C(l,r)\}. \end{aligned} $$

Limit of the argument

State compression is an implementation change, not the definition. Loop order is safe only after the uncompressed dependency graph is understood.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] dp[l][r]=\min_{l\le k<r}\{dp[l][k]+dp[k+1][r]+C(l,r)\} \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Sun 14 November 2010. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.