KnuthDP

When doing DP on intervals: a[i][j] = min_i < k < j(a[i][k] + a[k][j]) + f(i, j), where the (minimal) optimal k increases with both i and j, one can solve intervals in increasing order of length, and search k = p[i][j] for a[i][j] only between p[i][j-1] and p[i+1][j]. This is known as Knuth DP. Sufficient criteria for this are if f(b,c) ≤ f(a,d) and f(a,c) + f(b,d) ≤ f(a,d) + f(b,c) for all a ≤ b ≤ c ≤ d. Consider also: LineContainer (ch. Data structures), monotone queues, ternary search.

Time: O(N²) 0 lines

content/various/KnuthDP.h — Simon Lindholm, source: http://codeforces.com/blog/entry/8219