动态规划题目笔记（一）：LeetCode

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        size=len(s)
        assert size>0
        word_set={word for word in wordDict}
        dp=[False for _ in range(size+1)]
        dp[0]= True #保证空字符串为True

        for r in range(1,size+1):
            for l in range(r):
                #划分子问题，当子单词的孙子单词左右都为True时
                #说明几个孙子单词都在word_set，即这个子单词划分成功
                #将这个子单词标记为True，再上升最终将整个str标记为True
                if dp[l] and s[l:r] in word_set:
                    dp[r]=True
                    break #提升效率，r已经为True，l不必继续
        return dp[-1]

152. Maximum Product Subarray

Given an integer array?nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation:?[2,3] has the largest product 6.

my writing：(time is 8972 ms)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        mx=-float(‘inf‘)
        for r in range(len(nums)):
            p_before=1
            for l in range(r,-1,-1):
                p_before*=nums[l]
                if p_before>mx:
                    mx=p_before
        return mx

big lao writing：(time is 56ms)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        max_dp = [1] * (n + 1)
        min_dp = [1] * (n + 1)
        ans = float(‘-inf‘)

        for i in range(1, n + 1):
            max_dp[i] = max(max_dp[i - 1] * nums[i - 1],
                             min_dp[i - 1] * nums[i - 1], nums[i - 1])
            min_dp[i] = min(max_dp[i - 1] * nums[i - 1],
                            min_dp[i - 1] * nums[i - 1], nums[i - 1])
            ans = max(ans, max_dp[i])
        return ans

动态规划题目笔记（一）：LeetCode

原文：https://www.cnblogs.com/shitianfang/p/12631002.html