詳解最小m段和問題
最小m段和問題（數組分段和最大值最小問題）
問題描述：給定n個整數組成的序列，現在要求將序列分割為m段，每段子序列中的數在原序列中連續排列。如何分割才能使這m段子序列的和的最大值達到最小？
清潔工：假設有n個房間，清潔每個房間耗時用一個數組表示，10、20、30、40、50、60、70、80、90，安排m個清潔工，將連續的房間分成m份，每部分耗時求和，其最大值為此種分法的總耗時。求最快的耗時是多少。例如3個清潔工的話，10 20 30 40 50 | 60 70 | 80 90，此時是最快的，耗時為170。
裝桶：把數據按順序裝入桶中，m即是給定的桶數，問桶的容量至少應該為多少才能恰好把這些數裝入m個桶中
思路
先考慮最簡單的情況，假設有 \(1\) 個數，只有一個桶，\(m=1\)：至少需要容量為該數的值；
-
如果 \(n\) 個數，只有一個桶，\(m=1\)：至少需要容量為 \(n\) 個數之和；
-
如果 \(2\) 個數，兩個桶，\(m=2\)：至少需要容量為兩數之間最大值
-
如果 \(t\) 個數，兩個桶，\(m=2\) 呢？
我們將 \(t\) 個數劃分為兩份，隨機選一個劃分位置 \(k\)
10, 20, 30, 40, | 50, 60, 70, 80, 90
就變成兩部分： \(k\) 個數分到 1 個桶；\(t-k\) 個數分到一個桶
最少所需容量為 \(f(t,2) = min\{max[f(k,1),f(t-k,1)]\},1\leq k < t\)，其中 \(f(t-k,1)\) 表示後 \(t-k\) 個數之和，表示為\(f(t-k,1) = f(t，1)-f(k,1)\)
- 現在考慮 \(n\) 個數，\(m\) 個桶：
我們同樣將 \(n\) 個數劃分為兩份，即前 \(m-1\) 個桶和最後 \(1\) 個桶，隨機選一個劃分位置 \(k\)：
\]
可以使用遞歸求解了，但是太耗時。我們使用動態規劃填表就可以搞定了：
\]
可以用行表示對應的數字，列表示桶的數目，對1,2,3,4,5，兩個桶：
| 桶1 | 桶2 | |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 3 | 2 |
| 3 | 6 | 3 |
| 4 | 10 | 7 |
| 5 | 15 | 9 |
coding：
#---python
#動態規劃
# dp[i][j] = min(max(dp[k][j-1],dp[i][1]-dp[k][1]))
def dp_minMsum(nums,m):
n = len(nums)
dp = [[float('inf')]*(m+1) for _ in range(n+1)]
#初始化
for i in range(1,n+1):#只有一個桶
dp[i][1] = sum(nums[:i])
for j in range(1,b+1):#只有一個數
dp[1][j] = nums[0]
for i in range(2,n+1):
for j in range(2,m+1):
for k in range(1,i+1):
dp[i][j] = min(dp[i][j],max(dp[k][j-1],dp[i][1]-dp[k][1]))
return dp[-1][-1]
測試下：
>>> nums = [5,3,2,4,1]
>>> m = 2
>>> dp_minMsum(nums,m)
8
>>> nums = [10, 20, 30, 40, 50, 60, 70, 80, 90]
>>> m=3
>>> dp_minMsum(nums,m)
170
複雜度
時間複雜度：\(O(MN^2)\)
空間複雜度：\(O(NM)\)
二分查找優化
給定當前的桶容量，可以計算出需要的最少桶數：
如果需要的桶數量大於給定的桶數量k，說明桶容量太小了，增大容量；
如果計算需要的桶數量小於等於k，說明桶容量可能大了（也可能正好是要找的最小桶容量）
- 在給定容量時，求需要桶數
- 二分搜索桶容量
coding：
#---python
#根據桶容量進行二分查找對應的桶數
def bs_minMsum(nums,m):
low = max(nums)#容量下界 最大元素
high = sum(nums)#容量上界 元素和
while low < high:
mid = low+(high-low)//2
buckets = get_buckets(nums,mid)
if buckets <= m:#該容量下桶數 小於 給定桶數。減小容量
high = mid
else: #桶數 大於 給定桶數。增大容量
low = mid +1
return low
def get_buckets(nums,volume):
buckets = 1
ans = 0
for num in nums:
ans += num
if ans > volume:
buckets += 1
ans = num
return buckets
複雜度
時間複雜度：\(O(Nlog(\sum n))\),\(\sum n\) 為給定數組的元素和
空間複雜度：\(O(1)\)
