152. 乘积最大子数组

https://leetcode-cn.com/problems/maximum-product-subarray/
如果都是正整数，那整个array都乘下来就是最大的，需要考虑的特殊情况是：

  1. 负整数， 会让结果从很大变成很小，但如果再来一个负整数，结果又会重新变的很大，所以需要同时保留一个最大的正数和最小的负数。
  2. 因为一旦array里包括0，那么整个数字都为0，所以如果出现0，应当排除，这就是为什么LINE 9max和min里加上了当前的num,这样不至于让current_max和current_min一直是0

Dynamic Programming - 图1
Dynamic Programming - 图2
Dynamic Programming - 图3

  1. class Solution:
  2.     def maxProduct(self, nums: List[int]) -> int:
  3.         if not nums:
  4.             return -1
  5.         current_pos = nums[0]
  6.         current_neg = nums[0]
  7.         final_max = nums[0]
  8.         for num in nums[1:]:
  9.             current_pos, current_neg = max(current_pos*num,current_neg*num,num), min(current_pos*num,current_neg*num,num)
  11.             if current_pos > final_max:
  12.                 final_max = current_pos
  13.         return final_max

剑指 Offer 49. 丑数

https://leetcode-cn.com/problems/chou-shu-lcof/
关于是下一个丑数一定是前面某个数乘2或者乘3或者乘5得到的，而且是这三个乘积里最小的一个，因为是要求紧接着的那个丑数。
从第一个开始，每当下一个丑数是用2,3,5某一个乘到的，那么2，3，5对应的point就应该加一个

  1. class Solution:
  2.     def nthUglyNumber(self, n: int) -> int:
  3.         dp = [1] * n
  4.         a ,b,c = 0,0,0
  5.         for i in range(1,n):
  6.             n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5
  7.             dp[i] = min(n2,n3,n5)
  8.             if dp[i] == n2: a+=1
  9.             if dp[i] == n3: b+=1
  10.             if dp[i] == n5: c+=1
  11.         return dp[-1]

10. 正则表达式匹配

https://leetcode-cn.com/problems/regular-expression-matching/

  1. class Solution:
  2.     def isMatch(self, s: str, p: str) -> bool:
  3.         '''
  4.         s : 等待匹配
  5.         p : regex
  6.         '''
  7.         if not p: return not s
  8.         if not s and len(p)==1: return False
  9.         # 数组长度多加一个是为了匹配字符串为空的情况
  10.         # 所以数组的下标-1才是字符串的下标
  11.         rows = len(s)+1
  12.         cols = len(p)+1
  13.         dp = [[False for _ in range(cols)] for _ in range(rows)]
  15.         # initialization
  16.         dp[0][0]=True # s and p are all empty, match
  17.         dp[0][1]=False # s is empty, p only have one char, not match
  18.         for c in range(2,cols): # s is empty, p longer than 2
  19.             j = c-1 # j for the index in string
  20.             if p[j]=='*':
  21.                 dp[0][c] = dp[0][c-2]
  23.         for x in range(1,rows): # s string be matched
  24.             i = x-1
  25.             for y in range(1,cols): # regex pattern
  26.                 j=y-1
  27.                 if s[i]==p[j] or p[j]=='.':
  28.                     dp[x][y]=dp[x-1][y-1]
  29.                 elif p[j]=='*':
  30.                     if p[j-1]==s[i] or p[j-1]=='.':
  31.                         dp[x][y]=dp[x][y-2] or dp[x-1][y]
  32.                     else:
  33.                         dp[x][y]=dp[x][y-2]
  34.                 else:
  35.                     dp[x][y]=False
  36.         return dp[rows-1][cols-1]

5. 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

  1. class Solution:
  2.     def longestPalindrome(self, s: str) -> str:
  3.         m = len(s)
  4.         # row is i, column is j
  5.         dp = [[False for _ in range(m)] for _ in range(m)]
  6.         max_len = 1
  7.         start = 0
  8.         for j in range(m):
  9.             for i in range(j+1):
  10.                 if s[i]==s[j]:
  11.                     if j -i < 3:
  12.                         dp[i][j] = True
  13.                     else:
  14.                         dp[i][j] = dp[i+1][j-1]
  15.                 else:
  16.                     dp[i][j] = False
  18.                 if dp[i][j] and j - i + 1 > max_len:
  19.                     max_len = j - i +1
  20.                     start = i
  21.         return s[start: start+max_len]

42. 接雨水

https://leetcode-cn.com/problems/trapping-rain-water/
动态规划的内存消耗比较高， 注意最左边的max_left是自己,最右边的max_right是自己
image.png

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         if not height:
  4.             return 0
  5.         length = len(height)
  6.         max_left, max_right = [0]*length, [0]*length
  7.         max_left[0] = height[0]
  8.         max_right[-1] = height[-1]
  9.         for i in range(1,length):
  10.             max_left[i] = max(max_left[i-1], height[i-1])
  11.         for i in range(length-2, -1, -1):
  12.             max_right[i] = max(max_right[i+1], height[i+1])
  13.         res = 0
  14.         for i in range(length):
  15.             low_bound = min(max_left[i],max_right[i])
  16.             res += max(0, low_bound-height[i])
  17.         return res

双指针解法：
从两边往中间扫，如果left_max > right_max就处理左边的列， 反之则处理右边的列

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         if not height:
  4.             return 0
  5.         left_max, right_max = 0, 0
  6.         res = 0
  7.         left = 0
  8.         right = len(height)-1
  9.         while left<=right:
  10.             if left_max < right_max:
  11.                 res += max(0, left_max-height[left])
  12.                 left_max = max(left_max,height[left])
  13.                 left+=1
  14.             else:
  15.                 res += max(0, right_max-height[right])
  16.                 right_max = max(right_max, height[right])
  17.                 right-=1
  18.         return res

数学解法， 不需要额外空间
如下图，从左往右遍历，不管是雨水还是柱子，都计算在有效面积内，并且每次累加的值根据遇到的最高的柱子逐步上升。面积记为S1。
从左往右遍历得S1，每步S1+=max1且max1逐步增大
同样地，从右往左遍历可得S2。
从右往左遍历得S2，每步S2+=max2且max2逐步增大
于是我们有如下发现，S1 + S2会覆盖整个矩形，并且：重复面积 = 柱子面积 + 积水面积
最终， 积水面积 = S1 + S2 - 矩形面积 - 柱子面积

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         if not height:
  4.             return 0
  5.         max_height = 0
  6.         left_area = 0
  7.         for h in height:
  8.             max_height = max(max_height, h)
  9.             left_area += max_height
  10.         max_height = 0
  11.         right_area = 0
  12.         for i in range(len(height)-1, -1, -1):
  13.             max_height = max(max_height, height[i])
  14.             right_area += max_height
  16.         return left_area + right_area - (max_height*len(height))- sum(height)

139. 单词拆分

https://leetcode-cn.com/problems/word-break/
如果用递归写，需要把结果memorized

  1. from functools import lru_cache
  2. class Solution:
  3.     def wordBreak(self, s: str, wordDict: List[str]) -> bool:
  4.         @lru_cache
  5.         def backtrack(s):
  6.             if not s:
  7.                 return True
  8.             res = False
  9.             for i in range(1, len(s)+1):
  10.                 if s[:i] in wordDict:
  11.                     res = backtrack(s[i:]) or res
  12.             return res
  13.         return backtrack(s)

动态规划：
判断一个字符串s的某个位置i是否可以被wordDict来表示，可以拆分为i之前某个位置j可以被wordDict表示，而且j:i之间的string在wordDict里
这里有一些优化方式和注意的点，比如

  1. base case, dp[0]=True, 所以数组长度是len(s)+1
  2. i不用从1开始遍历， 可以从单词长度最短的一个开始

  3. 当i长度大于最长的单词的时候，j也不用从0开始遍历，可以从最长单词的位置之后开始遍历，因为我们从最短单词长度开始遍历的，所以此时的j最为最长单词的位置，肯定是true的

    1. class Solution:
    2.  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    3.      if wordDict:
    4.          wordDict = sorted(wordDict, key=len)
    5.          min_len, max_len = len(wordDict[0]), len(wordDict[-1])
    6.      else:
    7.          min_len = max_len = 0
    8.      dp = [True] + [False] * len(s)
    9.      for i in range(min_len, len(s)+1):
    10.          for j in range(max(0,i-max_len), i):
    11.              if dp[j] and s[j:i] in wordDict:
    12.                  dp[i] = True
    13.                  break
    14.      return dp[-1]

    887. 鸡蛋掉落

    https://leetcode-cn.com/problems/super-egg-drop/
    根据基本状态转移方程先写一个超时的基本解

    1. class Solution:
    2.  def superEggDrop(self, K: int, N: int) -> int:
    3.      '''
    4.      dp[i][j], i floors, have j eggs
    5.      floors is row, eggs is column
    6.      '''
    7.      dp = [[999 for _ in range(K+1)] for _ in range(N+1)]
    8.      for i in range(N+1):
    9.          dp[i][0] = 0
    10.          dp[i][1] = i
    11.      for j in range(2,K+1):
    12.          dp[0][j] = 0
    13.          dp[1][j]=1
    15.      for i in range(2,N+1):
    16.          for j in range(2, K+1):
    17.              for k in range(1,i+1):
    18.                  dp[i][j] = min(dp[i][j], max(dp[k-1][j-1], dp[i-k][j]) + 1)
    19.      return dp[N][K]

    把对k的寻找改为二分查找

    91. 解码方法

    https://leetcode-cn.com/problems/decode-ways/

    1. class Solution:
    2.  def numDecodings(self, s: str) -> int:
    3.      if s.startswith('0'):
    4.          return 0
    6.      dp = [0] * (len(s) + 1)
    7.      dp[0], dp[1] = 1,1
    8.      for i in range(2,len(s)+1):
    9.          if s[i-1] == '0' and s[i-2] not in '12':
    10.              return 0
    11.          elif s[i-2:i] in ['10','20']:
    12.              dp[i] = dp[i-2]
    13.          elif '10' < s[i-2:i] < '27':
    14.              dp[i] = dp[i-1] + dp[i-2]
    15.          else:
    16.              dp[i] = dp[i-1]
    17.      return dp[-1]

    322. 零钱兑换

    https://leetcode-cn.com/problems/coin-change/
    比较容易想到的动态规划

    1. class Solution:
    2.  def coinChange(self, coins: List[int], amount: int) -> int:
    3.      dp = [0] + [amount+1]*amount
    4.      for i in range(1,amount+1):
    5.          for c in coins:
    6.              if i < c:
    7.                  continue
    8.              else:
    9.                  dp[i] = min(dp[i], dp[i-c]+1)
    10.      return dp[amount] if dp[amount] != amount+1 else -1

    绝了的

    1. class Solution:
    2.  def coinChange(self, coins: List[int], amount: int) -> int:
    3.      n = len(coins)
    4.      coins.sort(reverse=True)     # 先给硬币排序，降序
    5.      self.res = float("inf")      # 定义最小的使用硬币的数量为self.res
    7.      def dfs(index,target,count):   # 定义深度优先搜索算法
    8.          coin = coins[index]
    9.          if math.ceil(target/coin)+count>=self.res:
    10.              return
    11.          if target%coin==0:
    12.              self.res = count+target//coin
    13.          if index==n-1:return
    14.          for j in range(target//coin,-1,-1):
    15.              dfs(index+1,target-j*coin,count+j)
    17.      dfs(0,amount,0)
    18.      return int(self.res) if self.res!=float("inf") else -1

    300. 最长递增子序列

    https://leetcode-cn.com/problems/longest-increasing-subsequence/
    为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。
    状态方程 dp[i]为加上nums[i]的时候的最长递增子序列， 所以dp[i]为 0这个最好理解，但是时间复杂度比较高，为O(N^2)

    1. class Solution:
    2.  def lengthOfLIS(self, nums: List[int]) -> int:
    3.      if not nums:
    4.          return 0
    5.      dp = [1 for _ in range(len(nums))]
    6.      max_final = 1
    7.      for i in range(len(nums)):
    8.          max_sub = 0
    9.          for j in range(i):
    10.              if nums[j] < nums[i]:
    11.                  max_sub = max(max_sub, dp[j])
    12.          dp[i] = max_sub+1
    13.          max_final = max(max_final, dp[i])
    14.      return max_final

    优化时间复杂度， 引入贪心和二分查找

  1. class Solution:
  2.     def lengthOfLIS(self, nums: List[int]) -> int:
  3.         if not nums:
  4.             return 0
  5.         tail = [nums[0]]
  6.         for i in range(1, len(nums)):
  7.             if nums[i] > tail[-1]:
  8.                 tail.append(nums[i])
  10.             else:
  11.                 left = 0
  12.                 right = len(tail)-1
  13.                 while left < right:
  14.                     mid = left + (right-left)//2
  15.                     if tail[mid] < nums[i]:
  16.                         left = mid +1
  17.                     else:
  18.                         right = mid
  19.                 tail[left] = nums[i]
  20.         return len(tail)

198. 打家劫舍

https://leetcode-cn.com/problems/house-robber/
打家劫舍系列经典动态规划问题, 从第一题开始.
dp[i] 表示在前i间房子满足条件的情况下可以偷到的最大金额
对于第i间房子来说, 分两种情况, 1) 不偷, 则dp[i]=dp[i-1] 2)偷,那么第i-1是不能偷的 则dp[i] = dp[i-2] + nums[i]
所以转移方程是:
dp[n+1] = max(dp(n), dp(n-1)+nums[n+1])
dp[0] = 0 代表前0间房子, 动态规划中有很多时候, dp数组需要比输入数组长度+1
因为dp[n]只和dp[n-1],dp[n-2]相关, 所以我们可以引入两个变量pre和cur,将空间复杂度降低到O(1)