假設有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)