DFS+memorization, enhanced Python DP solution, 39-42ms

  • 0

    This is not necessarily a smart solution, but I did not see anyone use the same method to enhance DP, so I want to discuss this solution.

    Obviously, The best answer cannot be smaller than sum(nums) / m. Any subarray with sum smaller than sum(nums) / m will force another subarray with sum larger than it. To get the minimum largest sum, we can constrain the sum of each subarray close to sum(nums) / m.

    The recursion here will first find out the smallest subarray nums[:j-1] with sum larger than sum(nums) / m. Then two search branch will be open:

    1. consider nums[:j-1] as one of the subarray, recursively split the rest of array, nums[j:]
    2. consider nums[:j-2] as one of the subarray, whose sum is also close to sum(nums) / m but smaller. Also recursively split the rest of array, nums[j-1:]

    After the split, it is easy to conclude the answer of minimum largest sum.

    Use memorization to store the answer of state (m, i)
    I also try to prove the boundary of subarray sum is legal, but I still cannot find a strict enough proof. Please point out my mistake if you find any.

    class Solution(object):
        def splitArray(self, nums, m):
            :type nums: List[int]
            :type m: int
            :rtype: int
            avg = sum(nums) / m
            mem = {}
            return self.dfs(nums, m, avg, mem, 0)
        def dfs(self, nums, m, avg, mem, i):
            acc = 0
            j = i
            ret = 0
            if mem.has_key((m, i)):
                return mem[(m, i)]
            if m == 1:
                ret = sum(nums[j:])
                mem[(m, i)] = ret
                return ret
            if (len(nums) - j)  <= m:
                ret = max(nums[(-1 * m):])
            while (len(nums) - j) > m - 1 and acc <= avg:
                acc += nums[j]
                j += 1
            ret = max(acc, self.dfs(nums, m - 1, sum(nums[j:]) / (m - 1), mem, j))
            if j - i > 1:
                ret = min(ret, max(
                    acc - nums[j - 1],
                    self.dfs(nums, m - 1, sum(nums[j-1:]) / (m - 1), mem, j - 1)))
            mem[(m, i)] = ret
            return ret

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.