假设有n个点，我们要用k个矩形去覆盖所用的点，然后这k个矩形的面积要尽可能小
1）矩形的底是在x轴上的（其实就是直方图）
2）矩形的面积可以为0（就是一条与x轴垂直的线）
3）矩形不能重叠（边线与顶点也都不能重合）
有人可以帮我一下吗？想了半天都没想出来怎么用动态规划解决这个问题
将 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)
∑Xi 或 ∑Yi 就是
什么规划都不需要
∑Yi 是所有点到 X 轴的距离。设点的直径为 1，则 1*∑Yi 就是所有矩形的最小面积之和
同理，∑Xi 也是
由于你不允许矩形相交，所以只能取 ∑Yi 或 ∑Xi 的小者
又想了一下，其实我说的也不对，最小面积应该是 d * N，d>=1
其实是你缺少了一个先决条件: k < n