Python solution dp and binary search


  • 9

    First i try dp, while got TLE:(while if using java to implement dp, u may get AC...)

    import sys
    class Solution(object):
        def splitArray(self, nums, m):
            """
            :type nums: List[int]
            :type m: int
            :rtype: int
            """
            dp = [[sys.maxint]*(m) for _ in range(len(nums)+1)]
            acc = 0
            dp[0][0] = 0
            for i in range(1, len(nums)+1):
                acc += nums[i - 1]
                dp[i][0] = acc
    
            for j in range(m):
                dp[0][j] = 0
    
            for i in range(1, len(nums)+1):
                for i_ in range(i):
                    for j in range(1, m):
                        dp[i][j] = min(dp[i][j], max(dp[i_][j-1], dp[i][0]-dp[i_][0]))
            #print dp
            return dp[len(nums)][m-1]
    

    Then by binary search, got AC:

    class Solution(object):
        def splitArray(self, nums, m):
            """
            :type nums: List[int]
            :type m: int
            :rtype: int
            """
            def valid(mid):
                cnt = 0
                current = 0
                for n in nums:
                    current += n
                    if current>mid:
                        cnt += 1
                        if cnt>=m:
                            return False
                        current = n
                return True
    
            l = max(nums)
            h = sum(nums)
    
            while l<h:
                mid = l+(h-l)/2
                if valid(mid):
                    h = mid
                else:
                    l = mid+1
            return l
    

  • 0

    @HanMing.py I have fixed the test cases, your DP code should get AC now.


  • 0

    For the DP solution, I think you only need to go through j from 1 to min(m, i + 1) as
    dp[i][j] when i < j does not provide any useful information.


Log in to reply
 

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