dp

10 Regular Expression Matching

#Given an input string (s) and a pattern (p), implement regular expression #matching with support for '.' and '*'.
#'.' Matches any single character.
#'*' Matches zero or more of the preceding element.
class Solution:
    # 动规
    def isMatch(self, s: str, p: str) -> bool:      
        dp=[[False for i in range(len(p)+1)] for j in range(len(s)+1)]
        dp[0][0]=True
        for i in range(1,len(p)+1):
            if p[i-1]=='*':
                if i>=2:
                    dp[0][i]=dp[0][i-2]
        for i in range(1,len(s)+1):
            for j in range(1,len(p)+1):
                if p[j-1]=='.':
                    dp[i][j]=dp[i-1][j-1]
                elif p[j-1]=='*':
                    dp[i][j]=dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                else:
                    dp[i][j]=dp[i-1][j-1] and s[i-1]==p[j-1]
        return dp[len(s)][len(p)]
    #递归
    def isMatch(self, s: str, p: str) -> bool:
         if len(p)==0: return len(s)==0
         if len(p)==1 or p[1]!='*':
             if len(s)==0 or (s[0]!=p[0] and p[0]!='.'):
                 return False
             return self.isMatch(s[1:],p[1:])
         else:
             i=-1; length=len(s)
             while i<length and (i<0 or p[0]=='.' or p[0]==s[i]):
                 if self.isMatch(s[i+1:],p[2:]): return True
                 i+=1
             return False

45. Jump Game II

'''
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.
'''
class Solution: 
# 贪心 记录当前最远可以走到哪里，当 i 遍历到这个位置后，再看下此时最远又能到哪个位置，
# 如果还不到最后位置，step+1
    def jump(self, nums: List[int]) -> int:
        step = 0
        cur = 0
        last = 0
        for i in range(len(nums)):
            if i > cur:
                return -1
            if i > last:
                last = cur
                step += 1
            cur = max(cur, nums[i] + i) 
        return step

62 Unique Paths

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[-1][-1]

63 Unique Paths II

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1:
            return 0
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        
        dp = [[0] * n for _ in range(m)]
        
        dp[0][0] = 1
        for i in range(1, m):
            if obstacleGrid[i][0] == 0 and dp[i-1][0] == 1:
                dp[i][0] = 1
            else:
                dp[i][0] = 0
        for j in range(1, n):
            if obstacleGrid[0][j] == 0 and dp[0][j-1] == 1:
                dp[0][j] = 1
            else:
                dp[0][j] = 0
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

64 Minimum Path Sum

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        
        mini = [[0]*n for i in range(m)]
        mini[0][0] = grid[0][0]
        for i in range(1,m):
            mini[i][0] = mini[i-1][0] + grid[i][0]
        for j in range(1,n):
            mini[0][j] = mini[0][j-1] + grid[0][j]
            
        for i in range(1,m):
            for j in range(1,n):
                mini[i][j] = min(mini[i-1][j], mini[i][j-1]) + grid[i][j]
                
        return mini[-1][-1]

72 Edit Distance

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m = len(word1)
        n = len(word2)
        
        dp = [[0]* (n+1) for i in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
            
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)
        return dp[-1][-1]

79 Word Search

class Solution:
    
    def exist(self, board, path):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board: return False
        if path == []: return True
        m = len(board)
        n = len(board[0])
        self.visited = [[False]*n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if path[0] == board[i][j]:
                    if self.find(board, m, n, path[1:], i, j):
                        return True
        return False
    
    def find(self, board, rows, cols, path, i, j):
        if not path:
            return True
        self.visited[i][j] = True

        
        if i+1 < rows and board[i+1][j] == path[0] and not self.visited[i+1][j]:
            if self.find(board, rows, cols, path[1:], i+1, j):
                return True
        elif i-1 >= 0 and board[i-1][j] == path[0] and not self.visited[i-1][j]:
            if self.find(board, rows, cols, path[1:], i-1, j):
                return True
        elif j+1 < cols and board[i][j+1] == path[0] and not self.visited[i][j+1]:
            if self.find(board, rows, cols, path[1:], i, j+1):
                return True
        elif j-1 >= 0 and board[i][j-1] == path[0] and not self.visited[i][j-1]:
            if self.find(board, rows, cols, path[1:], i, j-1):
                return True
        else:
            self.visited[i][j] = False
            return False

132 Palindrome Partitioning II

'''
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
'''
设DP[i][j]表示第i个字符到第j个字符是否构成回文，若是，则DP[i][j]=1;若否，则DP[i][j]=0;如此，
根据回文的约束条件（对称性），DP[i][j]构成回文需满足：
   1、输入字符串s[i]==s[j],对称性；
   2、条件1满足并不能保证i到j构成回文，还须：（j-i）<=1或者DP[i+1][j-1]=1；即，i、j相邻或者
i=j，也就是相邻字符相等构成回文或者字符自身构成回文，如果i、j不相邻或者相等，i到j构成回文的
前提就是DP[i+1][j-1]=1.
     所以状态转移方程：DP[i][j]=(s[i]==s[j]&&(j-i<=1||DP[i+1][j-1]==1))。由于i必须小于j，
i>=0&&i<s.length().如此，DP[i][j]构成一个下三角矩阵，空间、时间复杂度均为O(n2),如下所示：
对于长度为4的字符串s=“baab”，其中红色部分为i>j，为无意义部分；绿色部分i==j，
即字符串自身必然构成回文，DP[i][j]=1;白色部分，为长度大于1的子串，需要状态转移方程进行判断。

image

当输入字符串所有可能的分割情况求出来之后，我们需要进一步寻找最少分割次数，我们可以用一个一维
数组来存储分割次数：设int[] cut=new int[s.length()+1],cut[i]表示第i个字符到最后一个字符所
构成的子串的最小分割次数，这里的i有约束条件，就是第i个位置必须是可进行回文分割的，
即DP[i][j]==1 (j>=i&&j<s.length()),故：

image.png

class Solution:
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        f = [i for i in range(n-1,-2,-1)]
        
        p = [[False]*n for i in range(n)]
        
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if ((s[i] == s[j]) and ((j - i <= 2) or (p[i+1][j-1]))):
                    p[i][j] = True
                    f[i] = min(f[i], f[j+1] + 1)
        return f[0]

198 House Robber

'''
不能偷挨着的
'''
class Solution:
    # method1 递归    
    def rob(self, nums):
        if nums == []:
            return 0
        if len(nums) <= 2:
            return max(nums)
        self.res = 0
        return self.tryrob(nums, 0)
              
    def tryrob(self, nums, index):
        if index >= len(nums):
            return 0
        for i in range(index, len(nums)):
            self.res = max(self.res, nums[i] + self.tryrob(nums, i+2), self.tryrob(nums, i+1))
        return self.res
      
    # method2 记忆化搜索
    '''
    def rob(self, nums):
        if nums == []:
            return 0
        if len(nums) <= 2:
            return max(nums)
        self.res = 0
        self.memo = [-1] * (len(nums)+1)
        return self.tryrob(nums, 0)       
        
    def tryrob(self, nums, index):
        if index >= len(nums):
            return 0
        if self.memo[index] != -1:
            return self.memo[index]
        for i in range(index, len(nums)):
            self.res = max(self.res, nums[i] + self.tryrob(nums, i+2), self.tryrob(nums, i+1))
        self.memo[index] = self.res
        return self.res
    '''
    
    # method3 动规
    '''
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums==[]:
            return 0
        if len(nums)<=2:
            return max(nums)
        p = [0] * len(nums)
        p[0] = nums[0]
        p[1] = max(nums[1], nums[0])
        for i in range(2, len(nums)):
            p[i] = max(p[i-2]+nums[i], p[i-1])
        return p[-1]
    '''

300 Longest Increasing Subsequence

class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return 1
        
        dp = [1] * len(nums)
        
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

312 Burst Balloons

'''
Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
'''
class Solution:
    # 递归 rec函数求 [L,R] 内可以取得的最大值 
    #maxCoins[0][n-1]=maxCoins[0][i-1] + maxCoins[i+1][n-1] + nums[left]*nums[i]*nums[right]
#     def maxCoins(self, nums: List[int]) -> int:
#         if not nums or len(nums) == 0:
#             return 0
        
#         self.mc = [[0] * len(nums) for _ in range(len(nums))]
        
#         return self.rec(nums, 0, len(nums)-1)
    
#     def rec(self, arr, L, R):
#         if L > R: return 0
#         if self.mc[L][R] != 0:
#             return self.mc[L][R]
#         res = 0
#         for i in range(L, R+1):
#             sum_ = 0
#             center = arr[i]
#             if L != 0:
#                 center *= arr[L-1]
#             if R != len(arr) - 1:
#                 center *= arr[R+1]
#             sum_ += center
#             sum_ += self.rec(arr, L, i-1)
#             sum_ += self.rec(arr, i+1, R)
#             res = max(res, sum_)
#         self.mc[L][R] = res
#         return res

# 也可以动态规划

343 Integer Break

'''
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
'''
class Solution:
    '''
    # method1 递归
    def integerBreak(self, n: int) -> int:
        self.res = -1
        return self.rec(n)
        
    def rec(self, n):
        if n == 1:
            return 1
        for i in range(1, n):
            self.res = max(self.res, i * self.rec(n-i), i*(n-i))
        return res
    '''
    '''
    # method2 记忆化搜索
    def integerBreak(self, n: int) -> int:
        self.res = -1
        self.memo = [-1] * (n+1)
        return self.rec(n)
    
    def rec(self, n):
        if n == 1:
            return 1
        if self.memo[n] != -1:
            return self.memo[n]
        
        for i in range(1, n):
            self.res = max(self.res, i * self.rec(n-i), i*(n-i))
        self.memo[n] = self.res
        return self.res
    '''
    # method3 动态规划
    def integerBreak(self, n: int) -> int:
        memo = [-1] * (n+1)
        memo[1] = 1
        for i in range(2, n+1):
            for j in range(1, i):  # j + (i-j)
                memo[i] = max(memo[i], j*(i-j), j*memo[i-j])
        return memo[n]

416 Partition Equal Subset Sum

'''
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
'''
class Solution:
    '''
    #递归
    def canPartition(self, nums: List[int]) -> bool:
        if len(nums) == 1 or sum(nums) % 2 == 1:
            return False
        
        target = sum(nums) // 2
        return self.trypatition(nums, 0, target)
        
    def trypatition(self, nums, index, value):
        if value == 0:
            return True
        if value < 0 or index > len(nums) -1:
            return False
        return self.trypatition(nums, index+1, value) or self.trypatition(nums, index+1, value-nums[index])
    '''
    '''
    #记忆化搜索
    def canPartition(self, nums: List[int]) -> bool:
        if len(nums) == 1 or sum(nums) % 2 == 1:
            return False
        
        target = sum(nums) // 2
        self.memo = [[-1] * (target+1) for _ in range(len(nums))]
        return self.trypatition(nums, 0, target)
        
    def trypatition(self, nums, index, value):
        if value == 0:
            return True
        if value < 0 or index > len(nums) -1:
            return False
        if self.memo[index][value] != -1:
            return self.memo[index][value] == 1
        if self.trypatition(nums, index+1, value) or self.trypatition(nums, index+1, value-nums[index]):
            self.memo[index][value] = 1
        else:
            self.memo[index][value] = 0
        return self.memo[index][value] == 1
    '''
    
    #动规
    def canPartition(self, nums: List[int]) -> bool:
        if len(nums) == 1 or sum(nums) % 2 == 1:
            return False
        
        target = sum(nums) // 2
        dp = [False] * (target+1)
        for i in range(0, target+1):
            if (nums[0] == i):
                dp[i] = True
        for i in range(1, len(nums)):
            for j in range(target, nums[i]-1, -1):
                dp[j] = dp[j] or dp[j-nums[i]]
        return dp[-1]

494 Target Sum

'''
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
'''
class Solution:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        nsum = sum(nums)
        if nsum < S or (S + nsum) % 2 != 0:
            return 0
        else:
            return self.solve(nums, (S + nsum) // 2)
        
    def solve(self, nums, target):
        dp = [0] * (target + 1)
        dp[0] = 1
        for n in nums:
            for i in range(target, n-1,-1):
                dp[i] += dp[i-n]
        return dp[target]