假如说

• 矩形在$x$轴，那
• 矩形的总和在任何时候都不应超过原始函数的值，

以下简单的动态规划算法将计算最多的最优集$k$矩形 wrt 最小二乘误差$O(n^2k)$时间和$O(nk)$最坏情况下的空间。尽管这对于大型企业来说似乎是令人望而却步的$n$，有一些改进意味着许多输入将花费更少的时间——如果有必要，一些捷径会以牺牲最优性为代价来改善运行时间。

定义$f(i, j)$是可以在子序列上实现的最小错误$1, \dots, i$($i \le n$) 最多使用$j \le k$矩形。为避免混淆哪些数据点由哪些矩形支持，假设所有矩形都在小数部分为 0.5 的位置开始和结束。还定义$g(i, j)$成为子序列可以实现的最小错误$i, ..., j$使用一个结束于的矩形$x$坐标$j + 0.5$并从任何位置开始$\ge i + 0.5$和$\le j - 0.5$并具有小数部分 0.5。最后，让$adjErr(i, j, h)$是范围内的残差平方和$i, ..., j$假设一个高度的矩形$h$跨越这个区域。然后：

$f(i, j) = \min_{0 \le m < j}{(f(m, j-1) + g(m+1, i))}$

$g(i, j) = \min_{i \le m < j}{(adjErr(i, m, 0) + adjErr(m+1, j, min_{m<r\le j}x_r))}$

$adjErr(i, j, h) = \sum_{m=i}^j(x_m - h)^2$

总体最低可能误差由给出。通过追溯 DP 矩阵，寻找允许取其最小值$f(n, k)$$m$$f(i, j)$

如果这有用，请发表评论，我会回来充实细节。