給定一個非負(fù)整數(shù)數(shù)組和一個整數(shù) m，你需要將這個數(shù)組分成 m 個非空的連續(xù)子數(shù)組。設(shè)計(jì)一個算法使得這 m 個子數(shù)組各自和的最大值最小。

注意:
數(shù)組長度 n 滿足以下條件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

示例:

輸入:
nums = [7,2,5,10,8]
m = 2

輸出:
18

解釋:
一共有四種方法將nums分割為2個子數(shù)組。
其中最好的方式是將其分為[7,2,5] 和 [10,8]，
因?yàn)榇藭r這兩個子數(shù)組各自的和的最大值為18，在所有情況中最小。

動態(tài)規(guī)劃

看到「將數(shù)組分割為 m 段，求……」就知道動態(tài)規(guī)劃該出場了。

令 dp[i][j] 表示將數(shù)組的前 i 個數(shù)分割為 j 段所能得到的最大連續(xù)子數(shù)組和的最小值。

考慮第 j 段的具體范圍，枚舉k，其中前 k 個數(shù)被分割為 j-1 段，而第 k+1 到第 i 個數(shù)為第 j 段。

這 j 段子數(shù)組中和的最大值，就等于 dp[k][j-1] 與 subSum(k+1,i) 中的較大值，其中 subSum(i,j) 表示數(shù)組 nums 中下標(biāo)落在區(qū)間 [i,j] 內(nèi)的數(shù)的和。

由于我們要使得子數(shù)組中和的最大值最小，因此可以列出如下的狀態(tài)轉(zhuǎn)移方程：

對于狀態(tài) dp[i][j]，由于我們不能分出空的子數(shù)組，因此合法的狀態(tài)必須有 i≥j。對于不合法（i < j）的狀態(tài)，由于我們的目標(biāo)是求出最小值，因此可以將這些狀態(tài)全部初始化為一個很大的數(shù)。

Code

class Solution:def splitArray(self, nums: List[int], m: int) -> int:length, subSum = len(nums), [0]dp = [[sys.maxsize for _ in range(m + 1)] for _ in range(length + 1)]dp[0][0] = 0for element in nums:subSum.append(subSum[-1] + element)for i in range(1, length + 1):for j in range(1, min(i, m) + 1):for k in range(i):dp[i][j] = min(dp[i][j], max(dp[k][j - 1], subSum[i] - subSum[k]))return dp[length][m]

復(fù)雜度分析

時間復(fù)雜度：O(n²×m)，其中 n 是數(shù)組的長度，m 是分成的非空的連續(xù)子數(shù)組的個數(shù)。總狀態(tài)數(shù)為 O(n×m)，狀態(tài)轉(zhuǎn)移時間復(fù)雜度 O(n)，所以總時間復(fù)雜度為 O(n²×m)。

空間復(fù)雜度：O(n \times m)O(n×m)，為動態(tài)規(guī)劃數(shù)組的開銷。

總結(jié)

以上是生活随笔為你收集整理的410. Split Array Largest Sum 分割数组的最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。