53. Maximum Subarray

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  3.         dp = 0       # 以nums[i]为结尾的子数组和，若为正代表可以做出正向贡献
  4.         res = -10001
  5.         for num in nums:
  6.             dp = dp + num if dp > 0 else num
  7.             res = max(res, dp)
  8.         return res
  • 时间复杂度：动态规划 - 图1
  • 空间复杂度：动态规划 - 图2

Follow up **线段树**？

121. Best Time to Buy and Sell Stock

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         min_price = prices[0]
  4.         profit = 0
  6.         for price in prices[1:]:
  7.             min_price = min(min_price, price)
  8.             profit = max(profit, price - min_price)
  10.         return profit
  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  3.         dp0 = 0                              # 始终未持股
  4.         dp1 = -prices[0]                     # 持股
  5.         dp2 = 0                              # 持股后卖出
  7.         for price in prices[1:]:             # 买入 and 卖出
  8.             dp1, dp2 = max(dp1, dp0 - price), \
  9.                        max(dp2, dp1 + price)
  10.         return max(dp0, dp2)                 # 不持股时拥有收益
  • 时间复杂度：动态规划 - 图3
  • 空间复杂度：动态规划 - 图4

5. Longest Palindromic Substring

数据范围是动态规划 - 图5，暴力解法（枚举所有子串动态规划 - 图6，再判断是否是回文动态规划 - 图7）复杂度为动态规划 - 图8，显然不可行。
Approach I** 动态规划
长度为动态规划 - 图9的字符串，必然是回文串；
长度为动态规划 - 图10的字符串，如果两个字符相同则为回文串；
如果一个字符串（子串）本身是回文串，那么在其两端加上相同的字符，必定构成一个新的回文串。
考虑使用二维动态规划**，定义动态规划 - 图11表示动态规划 - 图12的子串是否是回文串：

  • 长度动态规划 - 图13和动态规划 - 图14的情况作为初始化
  • 转移方程：动态规划 - 图15
  • 动态规划 - 图16是动态规划 - 图17左下方的格子，故动态规划 - 图18需要逆向遍历，而动态规划 - 图19需要正向遍历

动态规划实际上是自底向上的填表过程，本题中表格为动态规划 - 图20正方形，实际上利用了其右上三角部分（包括对角线）。

  1. class Solution:
  2.     def longestPalindrome(self, s: str) -> str:
  3.         n = len(s)
  4.         res = s[0]
  5.         max_len = 1
  7.         dp = [[False for _ in range(n)] for _ in range(n)]
  8.         for i in range(n):                     # 长度为1的子串
  9.             dp[i][i] = True
  11.         for i in range(n-1, -1, -1):
  12.             for j in range(i+1, n):
  13.                 if (cur_len := j-i+1) == 2:    # 长度为2的子串
  14.                     dp[i][j] = s[i] == s[j]
  15.                 else:
  16.                     dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
  18.                 if dp[i][j] and cur_len > max_len:
  19.                     max_len = cur_len
  20.                     res = s[i:j+1]
  22.         return res
  • 时间复杂度：动态规划 - 图21
  • 空间复杂度：动态规划 - 图22

Approach II** 中心扩散法
同动态规划的思考路径，考虑枚举每一个扩散位置动态规划 - 图23，由中心向两边**扩散动态规划 - 图24判断是否是回文串。

  • 长度为奇数的子串，中心是单个字符；

  • 长度为偶数的子串，中心是两个字符。

    1. class Solution:
    2.   def longestPalindrome(self, s: str) -> str:
    4.       def find_bound(low, high):
    5.           while 0 <= low and high < len(s) and s[low] == s[high]:
    6.               low -= 1
    7.               high += 1
    8.           return low + 1, high - 1
    10.       start, end = 0, 0                  # 初始状态：字符串长度至少为1
    12.       for i in range(len(s)):
    13.           L1, R1 = find_bound(i, i)      # 从长度为1的子串开始扩散
    14.           if R1 - L1 > end - start:
    15.               start, end = L1, R1
    17.           L2, R2 = find_bound(i, i+1)    # 从长度为2的子串开始扩散
    18.           if R2 - L2 > end - start:
    19.               start, end = L2, R2
    21.       return s[start:end+1]

  • 时间复杂度：动态规划 - 图25

  • 空间复杂度：动态规划 - 图26

Approach III** 马拉车Manacher算法**
暂不掌握。

647. Palindromic Substrings

  1. class Solution:
  2.     def countSubstrings(self, s: str) -> int:
  3.         n = len(s)
  4.         res = 0
  5.         dp = [[False for _ in range(n)] for _ in range(n)]
  7.         for i in range(n-1, -1, -1):
  8.             for j in range(i, n):
  9.                 if i == j:                     # 子串长度==1
  10.                     dp[i][j] = True
  11.                 elif j == i + 1:               # 子串长度==2
  12.                     dp[i][j] = s[i] == s[j]
  13.                 else:                          # 子串长度>=3
  14.                     dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
  16.                 if dp[i][j]:
  17.                     res += 1
  19.         return res
  • 时间复杂度：动态规划 - 图27

  • 空间复杂度：动态规划 - 图28

    1. class Solution:
    2.   def countSubstrings(self, s: str) -> int:
    4.       def diffusion(left, right) -> int:
    5.           count = 0
    6.           while 0 <= left and right < n and s[left] == s[right]:
    7.               left -= 1
    8.               right += 1
    9.               count += 1
    10.           return count
    12.       n = len(s)
    13.       res = 0
    14.       for i in range(n):
    15.           res += diffusion(i, i) + diffusion(i, i+1)
    16.       return res

  • 时间复杂度：动态规划 - 图29

  • 空间复杂度：动态规划 - 图30

300. Longest Increasing Subsequence

Approach I** 动态规划
设动态规划 - 图31表示以动态规划 - 图32结尾的最长上升子序列**的长度，初始化为动态规划 - 图33。

  1. class Solution:
  2.     def lengthOfLIS(self, nums: List[int]) -> int:
  3.         dp = [1] * len(nums)
  5.         for i in range(1, len(nums)):
  6.             for j in range(i):
  7.                 if nums[j] < nums[i]:
  8.                     dp[i] = max(dp[i], dp[j] + 1)
  10.         return max(dp)
  • 时间复杂度：动态规划 - 图34
  • 空间复杂度：动态规划 - 图35

Approach I** 贪心 + 二分查找
可以更直观地考虑，不再以动态规划 - 图36表示以动态规划 - 图37结尾的最长上升子序列的长度，而是让动态规划 - 图38数组直接表示我们欲求得的最长上升子序列。在遍历原数组的过程中，将每一个元素动态规划 - 图39放置到最靠左的位置，使得动态规划 - 图40数组保持严格单调递增，即让动态规划 - 图41数组的增幅达到最慢。
以上，状态定义为：动态规划 - 图42表示长度为动态规划 - 图43的最长上升子序列的末尾元素的值（越小越好）。
因为所构造的动态规划 - 图44数组是严格递增的（有序），故可用二分查找来求得当前元素动态规划 - 图45的插入位置。最后返回动态规划 - 图46数组有效长度**即可。

动态规划 - 图47为什么不能使用单调栈？ 动态规划 - 图48我们的优化目标是，在遍历原数组的过程中构造最长上升子序列数组动态规划 - 图49，使得其变成更为紧凑（上升得最慢）的形式。若当前构造的数组（or单调栈）是动态规划 - 图50，欲插入的元素为动态规划 - 图51，单调栈会直接将其舍弃，而该题的二分查找会找到索引1，并将元素动态规划 - 图52替换，从而保证解题思路所定义的性质。

  1. class Solution:
  2.     def lengthOfLIS(self, nums: List[int]) -> int:
  3.         dp = []
  5.         for num in nums:
  6.             if not dp or dp[-1] < num:
  7.                 dp.append(num)
  8.             else:
  9.                 l, r = 0, len(dp) - 1
  10.                 while l < r:
  11.                     m = l + r >> 1
  12.                     if dp[m] < num:
  13.                         l = m + 1
  14.                     else:
  15.                         r = m
  16.                 dp[l] = num
  18.         return len(dp)
  • 时间复杂度：动态规划 - 图53
  • 空间复杂度：动态规划 - 图54

42. Trapping Rain Water

按行求：动态规划 - 图55，动态规划 - 图56是数组长度，动态规划 - 图57是数组中元素最高高度

  • 设置flag位来记录开始累计雨水的时刻，当动态规划 - 图58时开始记录

按列求：动态规划 - 图59

  • 当前列能够累积的雨水，取决于左侧最高列与右侧最高列的最小值。*****

Approach I** 动态规划
依然是采用按列求解的思路，不过使用额外的空间**记录每个位置的左右最高列，再通过一次遍历求得总雨水数。动态规划思想体现在左右最高列数组的构造上。

  1. class Solution:
  2.     def trap(self, heights: List[int]) -> int:
  3.         n = len(heights)
  4.         res = 0
  6.         l_max = [0] * n
  7.         for i in range(1, n):
  8.             l_max[i] = max(l_max[i-1], heights[i-1])
  10.         r_max = [0] * n
  11.         for i in range(n-2, -1, -1):
  12.             r_max[i] = max(r_max[i+1], heights[i+1])
  14.         for i in range(1, n-1):
  15.             res += max(0, min(l_max[i], r_max[i]) - heights[i])
  17.         return res
  • 时间复杂度：动态规划 - 图60
  • 空间复杂度：动态规划 - 图61

Approach II** 双指针
观察上述递推式：
动态规划 - 图62
再考虑动态规划中的滚动数组思想，我们能否将数组优化为普通变量？
动态规划 - 图63由动态规划 - 图64递推得来；动态规划 - 图65由动态规划 - 图66递推得来。考虑使用双指针动态规划 - 图67与动态规划 - 图68从数组两端向中心逼近，动态规划 - 图69与动态规划 - 图70记录当前位置左右最高列高度。
从左往右遍历到动态规划 - 图71位置时，动态规划 - 图72对于它而言是可信的，而动态规划 - 图73却是不可信的（动态规划 - 图74到动态规划 - 图75间可能有更高的列）。即对于该位置，左边最高列等于动态规划 - 图76，右边最高列大于或等于**动态规划 - 图77。

  1.                                    right_max
  2.  left_max                             __
  3.    __                                |  |
  4.   |  |__   __??????????????????????  |  |
  5. __|     |__|                       __|  |__
  6.         left                      right

反之亦然。

  1. class Solution:
  2.     def trap(self, heights: List[int]) -> int:
  3.         n = len(heights)
  4.         res = 0
  5.         l, r = 0, n - 1
  6.         l_max = r_max = 0
  8.         while l <= r:
  9.             if l_max < r_max:
  10.                 res += max(0, l_max - heights[l])
  11.                 l_max = max(l_max, heights[l])
  12.                 l += 1
  13.             else:
  14.                 res += max(0, r_max - heights[r])
  15.                 r_max = max(r_max, heights[r])
  16.                 r -= 1
  18.         return res
  • 时间复杂度：动态规划 - 图82
  • 空间复杂度：动态规划 - 图83

Approach III** 单调栈**

  1. class Solution:
  2.     def trap(self, heights: List[int]) -> int:
  3.         res = 0
  4.         stack = []                            # 非严格单调递减栈。存储index，为了计算W
  6.         for i, height in enumerate(heights):
  7.             while stack and heights[stack[-1]] < height:
  8.                 idx_down = stack.pop()
  9.                 if stack:                     # 栈为空，不能存储任何雨水
  10.                     W = i - stack[-1] - 1
  11.                     H = min(height, heights[stack[-1]]) - heights[idx_down]
  12.                     res += W * H
  13.             stack.append(i)
  15.         return res
  • 时间复杂度：动态规划 - 图84
  • 空间复杂度：动态规划 - 图85

72. Edit Distance

Approach I** 动态规划
设动态规划 - 图86表示从动态规划 - 图87转换到动态规划 - 图88需要的步骤数**。

  • 动态规划 - 图89表示insert操作
  • 动态规划 - 图90表示delete操作
  • 动态规划 - 图91表示replace操作

添加额外的一行一列以表示 动态规划 - 图92 与子串互相转化的情况。
76574ab7ff2877d63b80a2d4f8496fab3c441065552edc562f62d5809e75e97e-Snipaste_2019-05-29_15-28-02.png

  1. class Solution:
  2.     def minDistance(self, word1: str, word2: str) -> int:
  3.         m, n = len(word1), len(word2)
  4.         dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
  6.         for i in range(1, m+1):
  7.             dp[i][0] = i
  8.         for j in range(1, n+1):
  9.             dp[0][j] = j
  11.         for i in range(1, m+1):
  12.             for j in range(1, n+1):
  13.                 if word1[i-1] == word2[j-1]:
  14.                     dp[i][j] = dp[i-1][j-1]
  15.                 else:
  16.                     dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
  18.         return dp[-1][-1]
  • 时间复杂度：动态规划 - 图94
  • 空间复杂度：动态规划 - 图95

Approach II** dfs**

from functools import lru_cache

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        @lru_cache(None)
        def dfs(i, j):
            if i == 0:
                return j
            if j == 0:
                return i
            if word1[i-1] == word2[j-1]:
                return dfs(i-1, j-1)
            else:
                insert = dfs(i, j-1)
                delete = dfs(i-1, j)
                replace = dfs(i-1, j-1)
                return 1 + min(insert, delete, replace)

        m, n = len(word1), len(word2)
        return dfs(m, n)

1143. Longest Common Subsequence

Approach I** 动态规划
动态规划 - 图96表示动态规划 - 图97与动态规划 - 图98的最长公共子序列**的长度。

  • 动态规划 - 图99的边界情况（即有一个子序列是动态规划 - 图100），值为动态规划 - 图101

  • 转移方程取决于动态规划 - 图102和动态规划 - 图103是否相等（见代码）

    class Solution:
  def longestCommonSubsequence(self, text1: str, text2: str) -> int:
      m, n = len(text1), len(text2)
      dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

      for i in range(1, m+1):
          for j in range(1, n+1):
              if text1[i-1] == text2[j-1]:
                  dp[i][j] = 1 + dp[i-1][j-1]
              else:
                  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

      return dp[-1][-1]

  • 时间复杂度：动态规划 - 图104

  • 空间复杂度：动态规划 - 图105

Approach II** dfs**

from functools import lru_cache

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @lru_cache(None)
        def dfs(i, j):
            if i == 0 or j == 0:
                return 0

            if text1[i-1] == text2[j-1]:
                return 1 + dfs(i-1, j-1)
            else:
                return max(dfs(i-1, j), dfs(i, j-1))

        m, n = len(text1), len(text2)
        return dfs(m, n)

718. Maximum Length of Repeated Subarray

动态规划 - 图106：以动态规划 - 图107和动态规划 - 图108为结尾的公共子数组的最大长度。

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        res = 0
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if nums1[i-1] != nums2[j-1]:
                    dp[i][j] = 0
                else:
                    dp[i][j] = 1 + dp[i-1][j-1]
                    res = max(res, dp[i][j])

        return res
  • 时间复杂度：动态规划 - 图109
  • 空间复杂度：动态规划 - 图110
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        res = 0
        dp = [0] * (n + 1)

        for i in range(1, m+1):
            for j in range(n, 0, -1):
                if nums1[i-1] != nums2[j-1]:
                    dp[j] = 0
                else:
                    dp[j] = 1 + dp[j-1]
                    res = max(res, dp[j])

        return res
  • 时间复杂度：动态规划 - 图111
  • 空间复杂度：动态规划 - 图112

152. Maximum Product Subarray

数组中元素满足动态规划 - 图113，存在负数，故考虑增加一个状态定义：

  • 动态规划 - 图114：以动态规划 - 图115结尾的子数组的最小乘积
  • 动态规划 - 图116：以动态规划 - 图117结尾的子数组的最大乘积

只依赖于上一时刻的状态，故可进行空间优化。

实际上dp_min与dp_max的更新需要考虑当前num的正负，但由于Python的语言特性，可以将三种情况同时写在min()和max()方法中，简化了代码。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        dp_min = [11] * len(nums)
        dp_max = [-11] * len(nums)
        dp_min[0] = dp_max[0] = nums[0]

        for i, num in enumerate(nums[1:], start=1):
            dp_min[i] = min(num, num * dp_min[i-1], num * dp_max[i-1])
            dp_max[i] = max(num, num * dp_min[i-1], num * dp_max[i-1])

        return max(dp_max)
  • 时间复杂度：动态规划 - 图118
  • 空间复杂度：动态规划 - 图119

注意必须同时更新dp_min与dp_max，类似于梯度下降法中更新参数动态规划 - 图120。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = dp_min = dp_max = nums[0]

        for i, num in enumerate(nums[1:], start=1):
            dp_min, dp_max = min(num, num * dp_min, num * dp_max), \
                             max(num, num * dp_min, num * dp_max)
            res = max(res, dp_max)

        return res
  • 时间复杂度：动态规划 - 图121
  • 空间复杂度：动态规划 - 图122

32. Longest Valid Parentheses *

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s or len(s) < 2:
            return 0

        n = len(s)
        dp = [0] * n

        for i in range(1, n):
            # 以'('结尾的子串有效长度必定是0
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = 2
                    if i-2 >= 0:
                        dp[i] += dp[i-2]
                elif s[i-1] == ')':
                    if (j := i-1 - dp[i-1]) >= 0 and s[j] == '(':
                        dp[i] = 2 + dp[i-1]
                        if j - 1 >= 0 and s[j-1] == ')':
                            dp[i] += dp[j-1]

        return max(dp)
  • 时间复杂度：动态规划 - 图123
  • 空间复杂度：动态规划 - 图124

62. Unique Paths

动态规划 - 图125：到达位置动态规划 - 图126可能的方案数。
转移方程：动态规划 - 图127，当前位置只依赖于左侧和上侧，故使用滚动数组进行空间优化。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[-1]
  • 时间复杂度：动态规划 - 图128
  • 空间复杂度：动态规划 - 图129
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @lru_cache(None)
        def dfs(i, j):            # 到达位置(i, j)的路径总条数
            if i == 0 or j == 0:
                return 1

            return dfs(i - 1, j) + dfs(i ,j - 1)

        return dfs(m - 1, n - 1)

63. Unique Paths II

设有障碍物，两种方法的关键都在于初始化起点。

class Solution:
    def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
        @lru_cache(None)
        def dfs(i, j):
            if grid[i][j] or i < 0 or j < 0:
                return 0
            if i == 0 and j == 0:
                return 1

            return dfs(i-1, j) + dfs(i, j-1)

        m, n = len(grid), len(grid[0])
        return dfs(m-1, n-1)

class Solution:
    def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
        if grid[0][0]:
            return 0

        m, n = len(grid), len(grid[0])
        dp = [1] + [0] * (n - 1)

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    dp[j] = 0
                    continue
                if j > 0:
                    dp[j] += dp[j-1]

        return dp[-1]

221. Maximal Square

动态规划 - 图130：以动态规划 - 图131为右下角的正方形（只包含1）的最大边长。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        len_side = 0

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                    len_side = max(len_side, dp[i][j])

        return len_side ** 2

空间优化：注意细节

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(n)] for _ in range(2)]
        len_side = 0

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i % 2][j] = 1
                    else:
                        dp[i % 2][j] = 1 + min(dp[(i-1) % 2][j-1], dp[(i-1) % 2][j], dp[i % 2][j-1])
                    len_side = max(len_side, dp[i % 2][j])
                else:
                    dp[i % 2][j] = 0

        return len_side ** 2
  • 时间复杂度：动态规划 - 图132
  • 空间复杂度：动态规划 - 图133优化到动态规划 - 图134

剑指 Offer 19. 正则表达式匹配

初始化动态规划 - 图135！
状态转移：


  1. class Solution:
 def isMatch(self, s: str, p: str) -> bool:
     s = ' ' + s
     p = ' ' + p

     m, n = len(s), len(p)
     dp = [[False for _ in range(n)] for _ in range(m)]
     dp[0][0] = True

     for j in range(2, n, 2):
         dp[0][j] = dp[0][j-2] and p[j] == '*'

     for i in range(1, m):
         for j in range(1, n):
             if p[j] == '*':
                 dp[i][j] = dp[i][j-2] or \
                            dp[i-1][j] and (s[i] == p[j-1] or p[j-1] == '.')
             else:
                 dp[i][j] = dp[i-1][j-1] and (s[i] == p[j] or p[j] == '.')

     return dp[-1][-1]
  • 时间复杂度：
  • 空间复杂度：

139. Word Break

动态规划 - 图136表示动态规划 - 图137能否由word_dict中的单词划分。

class Solution:
    def wordBreak(self, s: str, word_dict: List[str]) -> bool:
        word_dict = set(word_dict)
        s = ' ' + s
        n = len(s)
        dp = [True] + [False] * (n - 1)

        for j in range(1, n):
            for i in range(max(j-19, 1), j + 1):  # word最大长度是20，剪枝
                if (word := s[i:j+1]) not in word_dict:
                    continue

                if dp[i-1]:
                    dp[j] = True

        return dp[-1]
  • 时间复杂度：动态规划 - 图138，其中动态规划 - 图139恒为动态规划 - 图140
  • 空间复杂度：动态规划 - 图141

96. Unique Binary Search Trees

股票问题

123. Best Time to Buy and Sell Stock III

当不持股时，现金最多。 动态规划 - 图142 return max(dp0, dp2, dp4)
对应测试用例：
动态规划 - 图143
动态规划 - 图144 动态规划 - 图145 同一天不能同时卖出 & 买入

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0 = 0          # 初始状态，不持股
        dp1 = -prices[0] # 第一次买入
        dp2 = -inf       # 第一次买入后卖出
        dp3 = -inf       # 第二次买入
        dp4 = -inf       # 第二次买入后卖出

        for price in prices[1:]:
            dp1, dp2, dp3, dp4 = max(dp1, dp0 - price), \
                                 max(dp2, dp1 + price), \
                                 max(dp3, dp2 - price), \
                                 max(dp4, dp3 + price)

        return max(dp0, dp2, dp4)
  • 时间复杂度：动态规划 - 图146
  • 空间复杂度：动态规划 - 图147

188. Best Time to Buy and Sell Stock IV

使用长度为动态规划 - 图148的动态规划 - 图149数组来记录当前状态：

  • 初始态；
  • 买入动态规划 - 图150次，买入动态规划 - 图151次后卖出；
  • ……
  • 买入动态规划 - 图152次，买入动态规划 - 图153次后卖出。

使用变量diff来统一买入 or 卖出的情况。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if k == 0 or not prices:                   # 特判
            return 0
        k = min(k, n//2)

        dp = [0] + [-prices[0]] + [-inf] * (2*k - 1)

        for price in prices[1:]:
            for i in range(1, 2*k + 1):
                diff = -price if i & 1 else price  # 奇数：买入，偶数：卖出
                dp[i] = max(dp[i], dp[i-1] + diff)

        return max(dp)
  • 时间复杂度：动态规划 - 图154
  • 空间复杂度：动态规划 - 图155