leetcode410 分割数组最大值

题目链接

410. 分割数组的最大值 - 力扣（LeetCode）

解题思路

[将数组分割为m段，求......]是动态规划题目常见的问法。

本题中，我们可以令
f[i][j]表示数组前i个数分割为j段所能得到的最大连续子数组和的最小值。

在进行状态转移时，我们可以考虑第j段的具体范围。即我们可以枚举k，其中前k个数被分割为j-1段，而第k+1到第i个数为第j段。此时，这j段子数组中和的最大值，就等于f[k][j-1]与sub(k+1,i)中的较大值，其中sub（i，j）表示数组nums中下标落在区间[i,j]内的数的和。

由于我们要使得子数组中和的最大值最小，因此可以列出如下的状态转移方程

f[i][j] = min{max(f[k][j-1],sub(k+1,i))}，当i=1,k=0时

对于状态f[i][j]，由于我们不能分出空的子数组，因此合法的状态，必须要i>=j。对于不合法（i<j）的状态，由于我们的目标时求出最小值，因此可以将这些状态全部初始化一个很大的数。所以一旦我们从不合法状态进行转移不会对最外层产生影响。

此外，我们还需要将f[0][0]的值初始化为0。

解题代码

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        f = [[10 ** 18] * (m + 1) for _ in range(n + 1)]
        sub = [0]
        
        for elem in nums:
            sub.append(sub[-1] + elem)

        f[0][0] = 0
        for i in range(1,n+1):
            for j in range(1,min(i,m) + 1):
                for k in range(i):
                    f[i][j] = min(f[i] [j], max(f[k][j-1],sub[i] - sub[k]))
        
        return f[n][m]