LeetCode #120 #140 #53 #152 2018

Part 5 – 综合题

这部分为动态规划中没有明确分类的综合题，有难有易，后面字符串处理题目较难，掌握思想即可。这里为保证动态规划题目的完整性，在此稍作解析。

120. Triangle

https://leetcode.com/problems/triangle/description/

注意行数，元素下标和循环起止点的关系即可。从下向上遍历的好处是，最后剩下的只有三角尖的一个元素，即为我们要的结果。
代码如下：

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        pre = triangle[-1]
        for i in range(len(triangle) - 1)[::-1]:
            cur = triangle[i]
            for j in range(len(cur))[::-1]:
                cur[j] = min(pre[j], pre[j + 1]) + cur[j]
            pre = cur
        return pre[0]

140. Word Break II

https://leetcode.com/problems/word-break-ii/description/

动态规划用在剪枝部分，注意possible数组的使用。
代码如下：

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        res = []
        if not s or not wordDict or len(s) == 0 or len(wordDict) == 0:
            return res
        possible = [True] * (len(s) + 1)
        self.helper(s, wordDict, 0, possible, [], res)
        return res
    
    def helper(self, s, wordDict, start, possible, words, res):
        if start == len(s):
            res.append(' '.join(words))
            return
        for i in range(start, len(s)):
            piece = s[start:i + 1]
            if possible[i + 1] and piece in wordDict:
                words.append(piece)
                size = len(res)
                self.helper(s, wordDict, i + 1, possible, words, res)
                if size == len(res):
                    possible[i + 1] = False
                words.pop()

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/description/

提供2种解法。第一种，动态规划“局部最优和全局最优”解法；
代码如下：

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        local_max = global_max = nums[0]
        for i in range(1, len(nums)):
            local_max = max(nums[i], nums[i] + local_max)
            global_max = max(local_max, global_max)
        return global_max

第二种，使用Divide and Conquer技术的解法。

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        return self.helper(nums, 0, len(nums) - 1)
    
    def helper(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = (left + right) // 2
        leftSub = self.helper(nums, left, mid)
        rightSub = self.helper(nums, mid + 1, right)
        leftMax = nums[mid]
        temp = 0
        for i in range(left, mid + 1)[::-1]:
            temp += nums[i]
            leftMax = max(temp, leftMax)
        rightMax = nums[mid + 1]
        temp = 0
        for i in range(mid + 1, right + 1):
            temp += nums[i]
            rightMax = max(temp, rightMax)
        return max(leftSub, rightSub, leftMax + rightMax)

152. Maximum Product Subarray

https://leetcode.com/problems/maximum-product-subarray/description/

使用动态规划“局部最优和全局最优”解法。
代码如下：

class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        local_max = local_min = global_max = nums[0]
        for i in range(1, len(nums)):
            temp_local_max = local_max
            local_max = max(nums[i], nums[i] * local_min, nums[i] * local_max)
            local_min = min(nums[i], nums[i] * local_min, nums[i] * temp_local_max)
            global_max = max(local_max, global_max)
        return global_max