动态规划题目笔记（一）：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

221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:return 0
        h=len(matrix);w=len(matrix[0]);mx=0
        dp=[[0]*(w+1) for _ in range(h+1)]

        for i in range(h):
            for j in range(w):
                if matrix[i][j]=="1":
                    #根据左上方正方形选取最短的一个边作为当前可扩展的正方形的边
                    dp[i+1][j+1]=min(dp[i+1][j],dp[i][j+1],dp[i][j])+1
                    mx=max(mx,dp[i+1][j+1])
        return mx*mx

213. House Robber II

ou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
  because they are adjacent houses.

class Solution:
    def rob(self, nums: List[int]) -> int:
        #考虑两种情况
        #1，不选n+1个房子则dp[n+1]=dp[n]
        #2，选n+1个房子则dp[n+1]=dp[n-1]+nums[n+1]
        def my_rob(nums):
            cur,pre=0,0
            for num in nums:
                cur,pre=max(pre+num,cur),cur
            return cur
        #此处将环状转化为两个排列情况，选第一个就不选最后一个，选最后一个就不选第一个
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums)!=1 else nums[0]

279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

class Solution:
    def numSquares(self, n: int) -> int:
        dp=[i for i in range(n+1)]
        for i in range(n+1):
            dp[i]=i
            j=1
            while i-j*j>=0: #j*j代表平方，每次取上一个平方数的最小个数情况
                dp[i]=min(dp[i],dp[i-j*j]+1)
                j+=1
        return dp[n]

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n=len(nums)
        dp=[1 for _ in range(n+1)]
        
        for i in range(n):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)