如何用动态规划解决平面上的n个点用k个矩形覆盖的最小面积？

Question

假设有n个点，我们要用k个矩形去覆盖所用的点，然后这k个矩形的面积要尽可能小
1）矩形的底是在x轴上的（其实就是直方图）
2）矩形的面积可以为0（就是一条与x轴垂直的线）
3）矩形不能重叠（边线与顶点也都不能重合）

有人可以帮我一下吗？想了半天都没想出来怎么用动态规划解决这个问题

Answer 1

将 n 个点的坐标排序（x 为主键）

任取一点将 n 个点分成 2 组 n1 和 n2，求出 2 个面积 m1 和 m2

从 n1 中取出最后的一个点，放入 n2 中，再求出 2 个面积 m'1 和 m'2

如果 m'1+m'2 < m1+m2，则继续

分别对重组后的 n1 和 n2 做如上操作

直至满足 k 的数量要求，反之亦然

其实你很快就会发现最小面积就是前 k-1 个点的 (maxx - minx)*(maxy-miny) + (n-k-1)