WEEK3

leetcode :
no_62:

image.png

思路：
本题暴力递归去遍历所有情况会超时
如果发现 result（m，n） = result(m-1,n) + result(m,n-1) 这个特征式子就好做了

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = []
        for i in range(n):
            dp.append([])
            for j in range(m):
                dp[i].append(0)
        for i in range(m):
            dp[0][i] = 1
        for i in range(n):
            dp[i][0] = 1
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

no_121:

image.png

思路：类似游标，以一个start来记录假定的买入，单次循环，通过判定当前股票价格与假定的买入价格的大小来修改start，如果当前值小于start处的值，更新start，假定在此处买入；如果当前的值大于start处的值，得出一个假定的收益量，存入benifit中，最终去benifit中取max就是最大的利益

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == []:
            return 0
        benifit = []
        start = 0
        for i in range(len(prices)):
            if prices[i] - prices[start] < 0:
                start = i
                benifit.append(0)

            else:
                benifit.append(prices[i] - prices[start])
        return max(benifit)

no_122:

image.png

思路：因为没有任何限制调价，那么把所有的上涨都纳入收益那就是那就是最大收益

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == []:
            return 0
        # start = 0
        allBenifit = 0
        for i in range(len(prices)):
            if i!=0:
                if prices[i] > prices[i-1]:
                    allBenifit+=(prices[i]-prices[i-1])
                

        return allBenifit

no_123:

image.png

思路：动态规划的思想。dp表示最大收益量，应该有三个维度：
第一个维度记录天数，第二个维度记录当前是否持有股票，第三个维度记录当前已经卖出股票的次数。状态转移方程如代码所示，最终的最大值应该满足（最后一天，手上不持有股票，已经完成一次或者两次交易，不小于0）等几个条件。注意边界值。

class Solution(object):
   def maxProfit(self, prices):
      if prices == []:
          return 0
      dp = [[[0,0,0],[0,0,0]] for i in range(len(prices))]
      dp[0][0][0] = 0

      dp[0][1][0] = - prices[0]

      for item in dp[0]:
          for j in range(len(item)):
              if j > 0 :
                  item[j] = float('-inf')

      for i in range(1,len(prices)):
           dp[i][0][0] = 0
           dp[i][0][1] = max (dp[i-1][1][0] + prices[i] , dp[i-1][0][1])
           dp[i][0][2] = max(dp[i-1][1][1] + prices[i],dp[i-1][0][2])
           dp[i][1][0] = max(dp[i-1][0][0] - prices[i],dp[i-1][1][0])
           dp[i][1][1] = max(dp[i-1][0][1] - prices[i],dp[i-1][1][1])
           dp[i][1][2] = float('-inf')
       
      return max(0,dp[len(prices)-1][0][1],dp[len(prices)-1][0][2])

no_188: 买卖股票的最佳时机 4

image.png

思路：
这个也可以用类似于上一提的三维dp来做，区别在于最后一个维度应该时k+1维的，表示卖出了0次 - k次。
问题：会超出空间限制。
解决：把 k > len(prices) / /2 的情况拎出来讨论，此时交易次数足够大，用第122题的方法去解决即可。

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        def noK(prices):
            start = 0
            allBenifit = 0
            for i in range(len(prices)):
                if i!=0:
                    if prices[i] > prices[i-1]:
                        allBenifit+=(prices[i]-prices[i-1])
            return allBenifit
        if prices == []:
            return 0
        if len(prices) == 1:
            return 0
        if k > len(prices) // 2:
            return noK(prices)
        dp = [[[0 for j in range(k+1)] for i in range(2)]for i in range(len(prices))]
        
        dp[0][0][0] = 0
        dp[0][1][0] = -prices[0]

        for item in dp[0]:
            for j in range(len(item)):
                if j>0:
                    item[j] = float('-inf')
        
        for i in range(1,len(prices)):
            dp[i][0][0] = 0
            dp[i][1][k] = float('-inf')
            for j in range(k+1):
                if j>0:
                    dp[i][0][j] = max(dp[i-1][1][j-1] + prices[i],dp[i-1][0][j])
                if j<k:
                    dp[i][1][j] = max(dp[i-1][0][j] - prices[i] , dp[i-1][1][j])
        
        return max(0,max(dp[len(prices)-1][0]))

no_309:

image.png

dp是一个二维的，第一个维度表示天数，第二个维度表示状态，有三个状态：1 手上没有股票，2 手上有股票 3 冷冻期

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == [] :
            return 0
        dp = [[0,0,0] for i in range(len(prices))]
        dp[0][0] = -prices[0] # 第一天有股票
        dp[0][2] = 0
        dp[0][1] = 0
        for i in range(1,len(prices)):
            dp[i][0] = max(dp[i-1][2] - prices[i] , dp[i-1][0])
            dp[i][1] = dp[i-1][0] + prices[i]
            dp[i][2] = max(dp[i-1][1], dp[i-1][2])
        return max(dp[len(prices)-1][1],dp[len(prices)-1][2],0)

no_714:

image.png

跟前面的题类似的，出售时记得减去 fee 就行了

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        if prices == []:
            return 0
        dp = [[0,0] for i in range(len(prices))]
        # dp[天数][0：手上无股票，1：手上有股票]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1,len(prices)):
            dp[i][0] = max(dp[i-1][1] + prices[i] - fee , dp[i-1][0])
            dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i])
        
        return max(0,dp[len(prices)-1][0])

这周的leetcode题目很多涉及动态规划，感觉比前面两周的难了不少。

听课笔记：