【leetcode】410. Split Array Largest Sum

题目如下：

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these msubarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000

1 ≤ m ≤ min(50, n)

Examples:
Input:

nums = [7,2,5,10,8]

m = 2

Output:

18

Explanation:

There are four ways to split nums into two subarrays.

The best way is to split it into [7,2,5] and [10,8],

where the largest sum among the two subarrays is only 18.

解题思路：记dp[i][j] 为把 0~j个元素分成i段时最大的一段和，例如 nums = [7,2,5,10,8]，dp[0][1] 表示第0个元素和第一个元素组成子数组的第一段。这里有几个约束条件：如果i是最后一段，那么j的取值只能是len(nums)-1；如果不是最后一段，那么j后面必须留下(m-i)个元素，因为任何一段子数组的长度都不能为0。假设第i-1段的区间范围是 a~b，那么很显然有 dp[i][j] = min( dp[i][j] , max(dp[i-1][m] , sum[m:j] )) ，其中 a <= m <= b，这里的意思是 dp[i-1][m] 表示为把 0~个元素分成i-1段时最大的一段和，那么在m~j这段区间的和如果大于 dp[i-1][m] ，那么dp[i][j] 就应该等于 m~j这段区间的和，否则令dp[i][j] 等于dp[i-1][m] 。

代码如下：

class Solution(object):

    def splitArray(self, nums, m):

        """

        :type nums: List[int]

        :type m: int

        :rtype: int

        """

        val = []

        amount = 0

        for i in nums:

            amount += i

            val.append(amount)

        dp = [[float('inf')] * len(nums) for _ in range(m)]

        for i in range(len(nums) - m + 1):

            dp[0][i] = val[i]

        for i in range(1,m):

            if i == m - 1:

                start = len(nums) - 1

                end = len(nums)

            else:

                start = i

                end = len(nums) -  (m - i) + 1

            for j in range(start,end):

                for k in range(i-1,j):

                    dp[i][j] = min(dp[i][j],  max(dp[i-1][k],val[j] - val[k]))

        #print dp

        return dp[-1][-1]

巴特西

【leetcode】410. Split Array Largest Sum

最新文章

热门文章