动态规划.md

53，最大自序和，简单

dp[i] 只跟 dp[i-1] 有关，所以可以使用一个变量表示上一个值，每次取更新后的pre和上一次结果cur的最大值最为当前维护的最大值

时间复杂度：O(n)1

空间复杂度：O(1)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = -10**5
        pre = 0
        for i in range(len(nums)):
            # 要么与前面合并，要么自己开头
            pre = max(pre + nums[i], nums[i])
            cur = max(cur, pre)
        return cur

322，零钱兑换，中等

核心方法：动态规划

难点：dp[i] 定义为组成金额 i 所需的最少的硬币数量，dp[i] 对应的转移方程为

$F(i) = min_{j=0...n-1}F(i - c_j) + 1$

其中 $c_j$ 代表的是第 j 枚硬币的面值，当枚举最后一枚硬币面额是$c_j$，那么需要从 $i - c_j$这个金额的状态$F(i - c_j)$转移过来，在算上枚举的这枚硬币的数量1的贡献

• 复杂度分析
  • 时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
  • 空间复杂度：O(S)。数组 dp 需要开长度为总金额 S 的空间。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 初始化，定义dp数据的每个位置为无穷大，因为要求最小数量
        dp = [float('inf')] * (amount + 1)
		# 边界条件：金额为零的时候就没有面额可用
        dp[0] = 0
        
        for coin in coins:
            # 获取一个面额
            for x in range(coin, amount + 1):
                # 从该面额到全金额中获取一个面额
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1 

72，编辑距离，困难

核心方法：动态规划（解决两个字符串的动态规划问题，一般都是用两个指针i，j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模）

难点：

dp[i][j]定义为word1[0..i-1]变为words[0..j-1]的最小操作数，也就是word1的前i个字符串和word2的前j个字符串的编辑距离（前i个不包含第i个元素）

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # 使用dp数组，dp[i][j]表示从word1[..i]变为word2[..j]需要的最小操作数
        # 因为会考虑到两个数组为空的情况，所以dp数组的两个维度各加一个
        dp = [[float('inf')] * (n+1) for _ in range(m+1)]
    
        # 如果word1不为空，word2为空，word1需要都删掉，有几个字符就删掉几个，所以dp[m][0] = m
        for i in range(m+1):
            dp[i][0] = i
        # 如果word1为空，word2不为空，需要在word1中逐个插入len(word2)个字符，dp[0][n] = n
        for j in range(n+1):
            dp[0][j] = j
		# 如果word1，word2都为空，那么dp[0][0] = 0（在上面两种情况中都被包含了）
            
        for i in range(1, m+1):
            for j in range(1, n+1):
                # 由于i 和 j 是从1开始取的，所以回到两个数组中时，需要各自-1才能取到第0位
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]  # 跳过操作
                else:
                    dp[i][j] = min(dp[i][j-1] + 1,   # 插入操作
                                   dp[i-1][j] + 1,   # 删除操作
                                   dp[i-1][j-1] + 1) # 替换操作
        return dp[m][n]

（推荐使用）上述的，当两个字符不能匹配时，插入操作，删除操作，替换操作能够解释dp数组变化的情况，也就是两个指针分别从两个字符串的末尾开始向前移动时的操作。

另外一种解释是，两个字符串的编辑距离可以转化为以下三种操作：

• 在单词A中插入一个字符：D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符
• 在单词B中插入一个字符：D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符
• 修改单词A的一个字符：D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同。如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。
• 此时的状态转移方程为：
  • 若 A 和 B 的最后一个字母相同：
    • dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1])
  • 若 A 和 B 的最后一个字母不同：
    • dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)
  • 代码可以表示为

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        
        # 有一个字符串为空串，那么其操作数就是另一个字符串的长度
        if n * m == 0:
            return n + m
        
        # DP 数组
        D = [[0] * (m + 1) for _ in range(n + 1)]
        
        # 边界状态初始化（与上同）
        for i in range(n + 1):
            D[i][0] = i
        for j in range(m + 1):
            D[0][j] = j
        
        # 计算所有 DP 值
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                # 针对上面第二种状态转移
                left = D[i - 1][j] + 1
                # 针对上面第一种状态转移
                down = D[i][j - 1] + 1
                # 针对上面第三种状态转移
                left_down = D[i - 1][j - 1] 
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1
                # 取最小
                D[i][j] = min(left, down, left_down)
        
        return D[n][m]

300，最长递增子序列，中等

核心方法：动态规划，定义dp[i]为nums[0..i]的最长递增子序列的长度

难点：这里实际处理的是对象为i，但是与nums[i]比较的是索引i之前的所有的数。这里的状态转移是，找到当前最大递增子序列长度dp[i]，和比nums[i]小的数对应的索引j对应的最大递增子序列长度，谁大取谁

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 边界条件：dp[0] = 1，对dp数组的所有位置全部进行初始化
        dp = [1] * len(nums)
        # 因为dp[0] = 1，所以i从1开始取
        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)

对于时间复杂度为$O(nlogn)$的处理方式，可以参考如下方式：有一副扑克牌，我们像遍历数组那样从左至右一张张来处理这些扑克牌，最终要把这副牌分成若干份；处理的原则为：只能把点数小的牌压到点数比它大或者和它相等的牌上；如果当前牌点数较大没有可以放置的堆，就新建一个堆，把这张堆放进去；如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。

按照上述规则执行，可以算出最长递增子序列，牌的堆数就是最长递增子序列的长度。

1143，最长公共子序列，中等

核心方法：子序列问题，都要考虑使用动态规划的方法

难点：

• 定义：dp[i][j]表示text1[0..i-1]和text[0..j-1]的最长公共子序列

• base case：dp[0][..]和dp[..][0]都为0，有一个为空，那么最长公共子序列就为0

• 如果text1[i] == text2[j]，那么dp[i][j] = dp[i-1][j-1] + 1

• 如果text1[i] != text2[j]，那么说明两个字符串中有一个字符串是不在公共子序列中，需要看前一个在不在，也就是选取前面的最大值。没有选到的就是不在公共子序列里的字符。dp[i][j] = max(dp[i][j-1], dp[i-1][j])

• 时间复杂度：O(mn)，m，n分别是text1，text2的长度

• 空间复杂度：O(mn)，主要来自于dp数组

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]  # 考虑到了字符串为空的情况，行列都要+0
        # already initialize the element to 0
        for i in range(1, m+1):  # 因为加了0，就要取到m，所以这里是m+1
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:  # 使用索引减1，是因为索引从1开始，但要取到0
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

32，最长有小括号，困难

核心方法：动态规划，dp[i]表示以s[i]结尾的字符串中的最长有效括号数

难点：

• base case：dp[0] = 0，只有一个括号肯定是不完整的

• 当s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”，我们可以推出：dp[i]=dp[i−2]+2

• s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出：如果 s[i−dp[i−1]−1]=‘(’，那么 dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2。其中，i−dp[i−1]−1对应着“……))”中最后一个右括号的左括号，也就是这两个括号能够组成一对儿。在处理中，dp[i−dp[i−1]−2]表示去掉所有当前i对应的右括号，及对应它的前面的左括号，和包含在这两个括号内的所有有效括号，之后的有效括号，也就是往前走到当前右括号对应的左括号之前的位置。

  当然，如果往前走到当前右括号对应的左括号之前，就已经超出边界了，那么就不需要加上dp[i−dp[i−1]−2]这个数

• 时间复杂度： O(n)

• 空间复杂度： O(n)

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        dp = [0] * n
        if n == 0: return 0
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = dp[i-2] + 2
                elif i - dp[i-1] > 0 and s[i - dp[i-1] -1] == '(':
                    if i - dp[i-1] - 2 >= 0:
                        dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2
                    else:
                        dp[i] = dp[i-1] + 2
        return max(dp)

198，打家劫舍，中等

核心方法：动态规划，dp[i] 表示以nums[i]结尾的前i个房屋一共偷窃的最高金额

难点：

• 只有一个房屋，那么dp[0] = nums[0]
• 只有两个房屋，选择前两个房屋里钱多的那一个，那么dp[1] = max(nums[0], nums[1])
• 对于第i个房屋要不要抢，如果抢前两个，那就是dp[i-2] + nums[i]；如果抢前一个，那么就是dp[i-1]
• 所以选择大的那个，dp[i] = max(dp[i-1], dp[i-2]+nums[i])

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i] 表示以nums[i]结尾的前i个房屋一共偷窃的最高金额
        if len(nums) < 2: return nums[0]
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        return dp[len(nums)-1]

改进方法：当前元素只和前两个结果有关，那么分别维护两个变量，分别记录上一次和这一次的结果

注意：更新 first 和 second 时，要写在一行，同时进行更新

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 2: return nums[0]
        first = nums[0]
        second = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            first, second = second, max(first + nums[i], second)
        return second

213，打家劫舍2，中等

核心方法：头尾的两个房屋不能被同时打劫，要么选择[0..n-2]，要么选择[1..n-1]。构建内部函数，向函数中传递这两个范围的索引，然后将两个结果比较，选择较大的那个

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        def rob1(start, end):
            first = nums[start]
            second = max(nums[start], nums[start+1])
            for i in range(start+2, end+1):
                first, second = second, max(first+nums[i], second)
            return second

        if n == 1:
            return nums[0]
        elif n == 2:
            return max(nums[0], nums[1])
        else:
            return max(rob1(0, n-2), rob1(1, n-1))

70，爬楼梯，简单

核心方法：dp[i]表示爬到第i级台阶时的方案总数

难点：

• 如果踏上了第n级台阶，那上一步一定是在n-1级或n-2级，而踏上n-1级有dp[n-1]种走法，踏上n-2级有dp[n-2]种走法，所以dp[n]=dp[n-1]+dp[n-2]
• 注意边界条件：dp[0]按理说是不用爬，但是为了保证状态转移方程对dp[2]是成立的，那么这里定义dp[0]=1
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        # 定义dp[i]为爬i阶楼梯的方法数
        if n == 1: return 1
        if n == 2: return 2
        dp = [1] * (n+1)
        dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

使用两个变量替换掉dp数组

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution:
    def climbStairs(self, n: int) -> int:
        # 定义dp[i]为爬i阶楼梯的方法数
        if n == 1: return 1
        if n == 2: return 2
        first, second = 1, 1
        for i in range(2, n+1):
            first, second = second, first + second
        return second

这个状态转移方程其实就是斐波那契数列，可以加速计算的方式还有两种：

• 随着 n 的不断增大 O(n) 可能已经不能满足我们的需要了，我们可以用「矩阵快速幂」的方法把算法加速到 O(logn)。
• 我们也可以把 n 代入斐波那契数列的通项公式计算结果，但是如果我们用浮点数计算来实现，可能会产生精度误差。

746，使用最小花费爬楼梯，简单

核心方法：动态规划，定义dp[i]为爬i阶楼梯需要花费的最小体力数

时间复杂度：O(n)

空间复杂度：O(n)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        if n == 2: return min(cost[0:2])
        # 初始条件：既可以从第一个阶梯开始，也可以从第二个阶梯开始
        # 所以dp[0] = dp[1] = 1
        dp = [0] * (n+1)
        for i in range(2, n+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[n]

进行状态压缩：时间复杂度降为O(1)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 定义dp[i]为爬i阶楼梯的方法数
        n = len(cost)
        if n == 2: return min(cost[0:2])
        # 初始条件：既可以从第一个阶梯开始，也可以从第二个阶梯开始
        # 所以dp[0] = dp[1] = 1
        first, second = 0, 0 
        for i in range(2, n+1):
            first, second = second, min(second + cost[i-1], first + cost[i-2])
        return second

121，买卖股票的最佳时机1，简单

核心方法：一次遍历，计算每次到当天为止的最小股票价格和最大利润，最后返回的也是最大利润（一次买卖）

• 时间复杂度：O(n)，遍历了一遍数组。
• 空间复杂度：O(1)，使用了有限的变量。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice = float('inf')
        maxProfit = 0
        for price in prices:
            minPrice = min(minPrice, price)
            maxProfit = max(maxProfit, price - minPrice)
        return maxProfit

核心方法：动态规划，dp[i]表示前i天的最大利润

状态转移方程为：dp[i]=max(dp[i−1], prices[i]−minprice)，其中 minprice 初始化为prices第0个价格。

• 时间复杂度：O(n)，遍历了一遍数组。
• 空间复杂度：O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # if n == 0: return 0
        dp = [0] * n
        minPrice = prices[0]
        for i in range(1, n):
            minPrice = min(minPrice, prices[i])
            dp[i] = max(dp[i-1], prices[i] - minPrice)
        return dp[-1]

122，买卖股票的最佳时机2，简单

核心方法，动态规划，dp[i]表示前i天的最大利润。这一题与上面的区别在于可以多次买卖。

难点：

• 对于dp[i]来说，要么当时持有股票，那么不持有股票。
• 初始化两个变量dp0和dp1，dp0=0表示没有股票，dp1=-prices[i]表示持有股票。
• 对于dp0，前一天也是dp0状态，或者前一天是dp1状态，今天卖出一笔变成dp0状态
  • dp0 = max(dp0, dp1 + prices[i])
• 对于dp1，前一天也是dp1状态，或者前一天是dp0状态，今天买进一笔变成dp1状态
  • dp1 = max(dp1, dp0 - prices[i])

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0 = 0
        dp1 = - prices[0]
        for i in range(1, len(prices)):
            dp0 = max(dp0, dp1 + prices[i])
            dp1 = max(dp1, dp0 - prices[i])
        return max(dp0, dp1)

123，买卖股票的最佳时机3，困难

核心方法：动态规划，这一题与上面的区别在于只能参与两次买卖。

难点：只有两次买卖，说明共有以下5种情况

• dp0：一直不买（针对返回为0的情况）
• dp1：买入一笔
• dp2：买入一笔，卖出一笔
• dp3：买入两笔，卖出一笔
• dp4：买入两笔，卖出两笔

注意：四种状态转移的过程，如果每次变量都选择走右边，那相当于执行了按顺序执行了买入，卖出，买入，卖出。因为一天当中的股价是不变的，所以最终的收益也是不变的。如果股价一直下跌，那么每一轮的状态转移的结果（即收益）就一定是0，那么最终的收益也是0。所以不需要比较dp0

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: return 0
        # 初始化 
        dp0 = 0            # 没有买
        dp1 = - prices[0]  # 买入一笔
        # 因为第一天没有dp2，dp3，dp4，所以将他们全部初始化为负无穷
        dp2 = float('-inf')
        dp3 = float('-inf')
        dp4 = float('-inf')
        for i in range(1, len(prices)):
            dp1 = max(dp1, dp0 - prices[i])  # 每一次的状态转移和上一次，前一个状态有关
            dp2 = max(dp2, dp1 + prices[i])
            dp3 = max(dp3, dp2 - prices[i])
            dp4 = max(dp4, dp3 + prices[i])
        return dp4

1411，给N*3的网格图涂色的方法数，困难

核心方法：动态规划，定义dp[i][type]为i*3的网格中最后一个格子里填充的颜色类型为type的方案数。因为在填充第i行时，影响它的只有上面那一行，也就是i-1。

难点：

• 首先，type 本身是要满足要求的。每一行有 3 个网格，如果我们用 0, 1, 2 分别代表红黄绿，那么 type 可以看成一个三进制数，例如 $type=(102)_3$ 时，表示 33 个网格从左到右的颜色分别为黄、红、绿；
• 我们可以预处理出所有满足要求的 type。具体地，我们使用三重循环分别枚举每一个格子的颜色，只有相邻的格子颜色不相同时，type 才满足要求。
• 其次，f[i][type]应该等于所有 f[i−1][type ′ ] 的和，其中 type’ 和 type 可以作为相邻的行。也就是说，type’ 和 type 的对应位置不能相同。

class Solution:
    def numOfWays(self, n: int) -> int:
        mod = 10**9 + 7
        # 预处理出所有满足条件的 type
        types = list()
        for i in range(3):
            for j in range(3):
                for k in range(3):
                    if i != j and j != k:
                        # 只要相邻的颜色不相同就行，将其以十进制的形式存储
                        types.append(i * 9 + j * 3 + k)
        type_cnt = len(types)
        # 预处理出所有可以作为相邻行的 type 对，related相当于标记了两个type对之间能否成为相邻行
        # 这一步相当于初始化
        related = [[0] * type_cnt for _ in range(type_cnt)]
        for i, ti in enumerate(types):
            # 得到 types[i] 三个位置的颜色
            x1, x2, x3 = ti // 9, ti // 3 % 3, ti % 3
            for j, tj in enumerate(types):
                # 得到 types[j] 三个位置的颜色
                y1, y2, y3 = tj // 9, tj // 3 % 3, tj % 3
                # 对应位置不同色，才能作为相邻的行
                if x1 != y1 and x2 != y2 and x3 != y3:
                    related[i][j] = 1
         # 递推数组
         f = [[0] * type_cnt for _ in range(n + 1)]
         # 边界情况，第一行可以使用任何 type
         f[1] = [1] * type_cnt
         for i in range(2, n + 1):
             for j in range(type_cnt):
                 for k in range(type_cnt):
                     # f[i][j] 等于所有 f[i - 1][k] 的和
                     # 其中 k 和 j 可以作为相邻的行
                     if related[k][j]:
                         f[i][j] += f[i - 1][k]
                         f[i][j] %= mod
         # 最终所有的 f[n][...] 之和即为答案
         ans = sum(f[n]) % mod
         return ans

核心方法：递推优化

我们把满足要求的 type 都写出来，一共有 1212 种：

010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212

我们可以把它们分成两类：

ABC 类：三个颜色互不相同，一共有 6 种：012, 021, 102, 120, 201, 210；

ABA 类：左右两侧的颜色相同，也有 6 种：010, 020, 101, 121, 202, 212。

我们用 f[i][0] 表示 ABC 类，f[i][1] 表示 ABA 类。

1. 第 i - 1 行是 ABC 类，第 i 行是 ABC 类：以 012 为例，那么第 i 行只能是120 或 201，方案数为 2；

2. 第 i - 1 行是 ABC 类，第 i 行是 ABA 类：以 012 为例，那么第 i 行只能是 101 或 121，方案数为 2；

3. 第 i - 1 行是 ABA 类，第 i 行是 ABC 类：以 010 为例，那么第 i 行只能是 102 或 201，方案数为 2；

4. 第 i - 1 行是 ABA 类，第 i 行是 ABA 类：以 010 为例，那么第 i 行只能是 101，121 或 202，方案数为 3。

所以递推公式为：

f[i][0]=2*f[i−1][0]+2*f[i−1][1]

f[i][1]=2*f[i−1][0]+3*f[i−1][1]

class Solution:
    def numOfWays(self, n: int) -> int:
        mod = 10**9 + 7
        fi0, fi1 = 6, 6
        for i in range(2, n + 1):
            fi0, fi1 = (2 * fi0 + 2 * fi1) % mod, (2 * fi0 + 3 * fi1) % mod
        return (fi0 + fi1) % mod

139，单词拆分，中等

核心方法：dp[i], i 为字符串长度, dp[i]为True表示：可以拆分为一个或多个在字典中出现的单词

词表中的单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

状态转移过程：

• dp[0] 表示的是空字符串（认为可以匹配），所以dp数组的长度应该是n+1

• dp[j]表示上一个范围的字符串是否在词表当中，s[0..i]表示[0, i]区间内的字符串是否在s中

• 当dp[j]和s[0..i]在s中全部为True，当前dp[i]才会为True

• 时间复杂度：$O(n^{2})$
• 空间复杂度：$O(n)$

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp=[False]*(len(s)+1)
        dp[0]=True 
        for i in range(1,len(s)+1):    # 遍历背包 
            for j in range(0,i):       # 遍历物品
                if dp[j] and s[j:i] in wordDict:  # check substr
                    dp[i] = True
                    break   # 已经找到dp[i]存在拆分单词
        return dp[-1]

核心方法：上一步的动态规划是包含重复计算的。这里使用记忆化回溯，保存出现过的backtrack(s)

• 如果 s[0,⋯,i−1] 在 wordDict中，那么直接比较切割后的字符串的s[i:]区间是否在词表中，直接使用递归进行回溯

• 但是，注意这个装饰器，用作及时释放缓存

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        import functools
        # 用来做缓存，把相对耗时的函数结果进行保存，避免重复计算，不用的缓存会被释放
        @functools.lru_cache(None)  
        def backtrack(s):
            if len(s) == 0: return True  # 表示正好处理完毕了，所以返回True
            # 首先将res定义为False，如果字符串和字典能够完美对应，res会等于True，否则为False
            res = False
            for i in range(1, len(s)+1):
                if s[:i] in wordDict:
                    # 这里的or res是为了保证在已经找到一种结果情况下，要留住True；
                    # 否则的话，已经找到True结果就有可能被后面的False结果给覆盖掉
                    res = backtrack(s[i:]) or res
            return res
        return backtrack(s)

152，乘积最大子数组，中等

注意：当前位置的最优解未必是由前一个位置的最优解转移得到的。因为两个不相邻的负数乘积会变为正数，那么包含这两个负数的子数组有可能会大于不与负数进行结合的新数组的乘积。

• 核心方法：根据正负性进行分类讨论。

  当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。

  如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。

• 再维护一个 $dp_{\min}(i)$，它表示以第 i个元素结尾的乘积最小子数组的乘积

  $dp_{max}(i) = max_{i=1}^n(dp_{max}(i-1)*a_i, dp_{min}(i-1)*a_i, a_i)$

  $dp_{min}(i) = min_{i=1}^n(dp_{max}(i-1)*a_i, dp_{min}(i-1)*a_i, a_i)$

  相当于同时维护两个dp数组，$dp_{max}[i]$ 表示以nums[i]结尾的数组的最大乘积；$dp_{min}[i]$ 表示以nums[i]结尾的数组的最小乘积

• 时间复杂度：O(n)

• 空间复杂度：O(n)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        dp_max = [0] * len(nums)
        dp_min = [0] * len(nums)
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]
        for i in range(1, len(nums)):
            dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
            dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
        return max(dp_max)

dp[i]只与前一个dp[i-1]有关，所以可以选择两个变量分别保存每个结果

注意，每次需要两个额外的变量保存上一时刻的最大乘积和最小乘积

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # dp[i]表示以nums[i]结尾的数组的最大乘积
        dp_max = nums[0]
        dp_min = nums[0]
        max_ans = nums[0]
        for i in range(1, len(nums)):
            last_max, last_min = dp_max, dp_min
            dp_max = max(last_max * nums[i], last_min * nums[i], nums[i])
            dp_min = min(last_max * nums[i], last_min * nums[i], nums[i])
            max_ans = max(dp_max, max_ans)
        return max_ans

354，俄罗斯套娃信封问题，困难

核心思路：

• 首先我们将所有的信封按照 w 值第一关键字升序、h 值第二关键字降序进行排序；h 降序的原因是：因为一个w只能出一个h，所以同一个w的h们按降序排列，防止重复利用
• 随后我们就可以忽略 w 维度，求出 h 维度的最长严格递增子序列，其长度即为答案。

• 动态规划（参考最长递增子序列的状态转移）
  • 定义 dp[i] 表示 h 的前 i 个元素可以组成的最长严格递增子序列的长度
• 复杂度：
  • 时间：$O(n^2)$
  • 空间：O(n)

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        # 首先对宽度 w 进行升序排序，对于同样 w 的情况，对高度 h 进行排序
        envelopes.sort(key=lambda x: (x[0], -x[1]))
		
        # 剩下的步骤类似于求最长递增子序列
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                # 这里比较的是数组中的高度 h，需要保证 h 是严格递增的
                if envelopes[j][1] < envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

核心方法：基于二分查找的动态规划，推荐

设 f[j] 表示 h 的前 i 个元素可以组成的长度为 j 的最长严格递增子序列的末尾元素的最小值，如果不存在长度为 j 的最长严格递增子序列，对应的 f 值无定义。在定义范围内，可以看出 f 值是严格单调递增的，因为越长的子序列的末尾元素显然越大。

在进行状态转移时，我们考虑当前的元素 $h_i$：

• 如果 $h_i$ 大于 $f$ 中的最大值，那么 $h_i$ 就可以接在 f 中的最大值之后，形成一个长度更长的严格递增子序列；

• 否则我们找出 $f$ 中比 $h_i$ 严格小的最大的元素 $f[j_0]$ ，即 $f[j_0] < h_i \leq f[j_"{0+1}]$，那么 $h_i$ 可以接在 $f[j_0]$ 之后，形成一个长度为 $j_{0+1}$ 的严格递增子序列，因此需要对 $f[j_{0+1}]$ 进行更新：$f[j0+1]=h_i$

• 我们可以在 $f$ 上进行二分查找，找出满足要求的 $j_0$。在遍历所有的 $h_i$ 之后，$f$ 中最后一个有定义的元素的下标增加 1（下标从 0 开始）即为最长严格递增子序列的长度。

• 复杂度：

  • 时间：O(nlogn)，其中 n 是数组 envelopes 的长度，排序需要的时间复杂度为 O(nlogn)，动态规划需要的时间复杂度同样为 O(nlogn)。
  • 空间：O(n)，即为数组 ff 需要的空间。
  • 二分查找应该是可以手写的

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        if n == 0:
            return 0
        # w相等，按h降序，防止用多次。一个w只能用一个h
        envelopes.sort(key = lambda x: (x[0], -x[1]))  
        # LIS 中之存放排序后每个信封的高度h
        LIS = [envelopes[0][1]]
        for i in range(1, n):
            # 二分查找，找到当前h在LIS中的位置，其值在数组中位置
            # 这里的 w 已经是递增的了，所以这里可以忽略
            pos = bisect.bisect_left(LIS, envelopes[i][1])  
            if pos == len(LIS):
                # 如果这个位置就是LIS中的最后一个，那么直接将这个结果添加到LIS末尾
                LIS.append(envelopes[i][1])
            else:
                # 否则在对应位置将原有值进行替换，因为当前的更小
                LIS[pos] = envelopes[i][1]
        
        return len(LIS)

62，不同路径，中等

核心方法：定义dp[i][j]表示，从起始位置到 [i,j] 位置总共的路径数。

dp[0][0] = 1

• 边界条件：

  如果只是按行走，那么dp[0][i] = 1

  如果只是按列走，那么dp[i][0] = 1

• 状态转移：

  • 当 i > 0 且 j > 0 时，走到当前位置只能通过往右走或者往下走实现，所以dp[i][j] = dp[i-1][j] + dp[i][j-1]

时间复杂度：O(mn)

空间复杂度：O(mn)

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

核心方法：组合数学

从左上角到右下角的过程中，我们需要移动 m+n-2 次，其中有 m−1 次向下移动，n−1 次向右移动。因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数，计算 $C_{m+n-2}^{m-1}$

时间复杂度：O(m)。由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得m≤n，这样空间复杂度降低至 O(min(m,n))。

空间复杂度：O(1)O(1)。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

63，不同路径，中等

具体内容见下面

时间复杂度：O(mn)，mn分别为矩阵的长宽

空间复杂度：O(mn)

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        r, c = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * c for _ in range(r)]
        # 对第一行和第一列做初始化，有一个卡住了，后面全都是0
        for i in range(r):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = 1
            else:
                break
        
        for j in range(c):
            if obstacleGrid[0][j] != 1:
                dp[0][j] = 1
            else:
                break
        
        # 开始其他位置的遍历
        for i in range(1, r):
            for j in range(1, c):
                # 需要同时保证[i,j], [i-1,j], [i][j-1]全都不是障碍物，才能完成直接相加的状态转移
                # 否则，谁不是1，就加谁
                if obstacleGrid[i][j] != 1:
                    if obstacleGrid[i-1][j] != 1:
                        dp[i][j] += dp[i-1][j]
                    if obstacleGrid[i][j-1] != 1:
                        dp[i][j] += dp[i][j-1]
        return dp[r-1][c-1]

64，最小路径和，中等

核心方法：定义dp[i][j]为从起始位置走到[i,j]位置的最小总和

初始条件：dp[0][0] = grid[0][0]，且横向走和纵向走，对应位置都是上一个结果+当前遍历到的结果

状态转移：取向右走和向下走的最小值，再加上当前遍历到的结果

时间复杂度：O(mn)

空间复杂度：O(mn)

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

87，扰乱字符串，困难

核心方法：「扰乱字符串」的关系是具有对称性的，即如果 $s_1$ 是 $s_2$ 的扰乱字符串，那么 $s_2$ 也是 $s_1$ 的扰乱字符串。这种情况定义为【和谐】。

定义 $dp(s_1, s_2)$ 表示 $s_1$ 和 $s_2$ 是否「和谐」

• 如果 $s_1 = s_2$ 那么两个字符串和谐

• $s_1$ 和 $s_2$ 长度不同，一定不和谐（题目中已经说明两个字符串是长度相同的，所以这种情况不考虑）

• 如果 $s_1$ 中某个字符 c 出现了 $x_1$ 次，而 c 在 $s_2$ 中出现了 $x_2$ 次，且 $x_1 \neq x_2$ ，那么一定不和谐。

• 那么对于剩下的情况，可以从字符串的分割方法入手。==我们用 $s_1(x, y)$ 表示从 $s_1$ 从第 $x$ 个字符（从 $0$ 开始编号）开始，长度为 $y$ 的子串。==由于分割出的两个字符串不能为空串，那么其中一个字符串就是$s_1(0, i)$，另一个字符串是 $s_1(i, n-i)$

  • 如果一个字符串分割后没有交换，分割后两个字符串对应位置进行匹配。最外层为或运算，内层为与运算。只要内部有一个情况下为True，这个dp位置就为True

    $dp(s_1, s_2) = \lor_{i=1}^{n-1}(dp(s_1(0, i), s_2(0,i)) \land (dp(s_1(i,n-i),s_2(i, n-i))))$

  • 如果一个字符串分割后进行交换，分割后两个字符串不同位置进行匹配。$s_2$ 需要被分为 $s_2(0, n-i)$ 以及 $s_2(n-i, i)$，这样对应的长度才会相同。

• 细节：

  • 可以考虑使用「记忆化搜索」自顶向下地进行动态规划，这样我们只需要用题目中给定的两个原始字符串开始，递归地计算所有的 dp 值，而无需考虑计算顺序。

  • 由于我们使用记忆化搜索，因此我们需要把 $s _1$ 和 $s_2$ 作为参数传入记忆化搜索使用的递归函数。这样一来，在递归传递参数的过程中，会使用到大量字符串的切片、拷贝等操作，使得时空复杂度不那么优。本题中，由于给定原始字符串的长度不超过 3030，因此不会产生太大的影响，但我们还是要尽可能对代码进行优化。

    非常重要！ 我们将状态变更为 $dp(i_1, i_2, \textit{length})$ 表示第一个字符串是原始字符串从第 $i_1$ 个字符开始，长度为 length 的子串，也就是 $s_1$，第二个字符串是原始字符串从第 $i_2$ 个字符开始，长度为 $length$ 的子串，也就是$s_2$。可以发现，我们只是改变了表达 $s_1$ 和 $s_2$ 的方式，但此时我们只需要在递归时传递三个整数类型的变量，省去了字符串的操作；

• 时间复杂度：$O(n^4)$，其中 n 是给定的原始字符串的长度。动态规划中的状态 $dp(i_1, i_2, \textit{length})$ 有 3 个维度，对于每一个状态，我们需要 $O(n)$ 枚举分割位置，因此总时间复杂度为 $O(n^4)$

• 空间复杂度：$O(n^3)$，即为存储所有动态规划状态需要的空间。

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def dfs(i1: int, i2: int, length: int) -> bool:
            """
            字符串 s1 从 i1 开始，字符串 s2 从 i2 开始，子串的长度为 length，是否和谐
            """

            # 判断两个子串是否相等
            if s1[i1:i1+length] == s2[i2:i2+length]:
                return True
            
            # 判断是否存在字符 c 在两个子串中出现的次数不同
            if Counter(s1[i1:i1+length]) != Counter(s2[i2:i2+length]):
                return False
            
            # 枚举分割位置
            for i in range(1, length):
                # 不交换的情况
                if dfs(i1, i2, i) and dfs(i1 + i, i2 + i, length - i):
                    return True
                # 交换的情况
                if dfs(i1, i2 + length - i, i) and dfs(i1 + i, i2, length - i):
                    return True
        
            return False

        ans = dfs(0, 0, len(s1))
        dfs.cache_clear()
        return ans

368，最长整出子集，中等

核心方法：当我们对 nums 排好序并从前往后处理时，在处理到 nums[i] 时，我们希望知道位置 i 之前的下标已经形成的「整除子集」长度是多少，然后从中选一个最长的「整除子集」，将 nums[i] 接在后面（前提是符合倍数关系）。

nums[i] 能否接在 nums[j] 后面，取决于是否满足 nums[i] % nums[j] == 0 条件。

定义 f[i] 为考虑前 i 个数字，且以第 i 个数为结尾的最长「整除子集」长度。

• 如果在 i 之前找不到符合条件 nums[i] % nums[j] == 0 的位置 j，那么 nums[i] 不能接在位置 i 之前的任何数的后面，只能自己独立作为「整除子集」的第一个数，此时状态转移方程为 f[i] = 1；

• 如果在 i 之前能够找到符合条件的位置 j，则取所有符合条件的 f[j] 的最大值，代表如果希望找到以 nums[i] 为结尾的最长「整除子集」，需要将 nums[i] 接到符合条件的最长的 nums[j] 后面，此时状态转移方程为 f[i] = f[j] + 1。

定义 g[i] 为记录 f[i] 是由哪个下标的状态转移而来，如果 f[i] = f[j] + 1, 则有 g[i] = j。

当我们求得所有的状态值之后，可以对 f[] 数组进行遍历，取得具体的最长「整除子集」长度和对应下标，然后使用 g[] 数组进行回溯，取得答案。

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()  # 对数组进行排序
        n = len(nums)
        f, g = [0] * n, [0] * n  # 分别初始化两个数组
        for i in range(n):
            # 至少包含自身一个数，因此起始长度为 1，由自身转移而来
            length, prev = 1, i
            # 截止到同一个位置，取最长的整除子集
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    # 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」
                    if f[j] + 1 > length:
                        length = f[j] + 1
                        prev = j
            # 记录「最终长度」&「从何转移而来」
            f[i] = length
            g[i] = prev

        # 遍历所有的 f[i]，取得「最大长度」和「对应下标」
        max_len = idx = -1
        for i in range(n):
            if f[i] > max_len:
                idx = i
                max_len = f[i]
        
        # 使用 g[] 数组回溯出具体方案
        ans = []
        while len(ans) < max_len:
            ans.append(nums[idx])
            idx = g[idx]
        ans.reverse()
        return ans

264，丑数2，中等

核心方法：最小堆。首先将1放入堆中，连续n-1次从堆中获取堆顶元素，然后将这个元素的2倍，3倍和5倍放入堆中。第n次取出的堆顶元素就是我们要的第n个丑数。为了防止一个数被多次入堆和出堆，可以使用一个集合存放已经入过堆的元素。

• 时间复杂度：$O(n \log n)$。得到第 n 个丑数需要进行 n 次循环，每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素，因此每次循环的时间复杂度是 $O(\log n+\log 3n)=O(\log n)$，总时间复杂度是 $O(n \log n)$。

• 空间复杂度：O(n)。空间复杂度主要取决于最小堆和哈希集合的大小，最小堆和哈希集合的大小都不会超过 3n。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        factors = [2,3,5]
        added = set()
        minheap = [1]
        heapq.heapify(minheap)
        for i in range(n-1):
            cur = heapq.heappop(minheap)
            for factor in factors:
                nxt = cur * factor
                if nxt not in added:
                    heapq.heappush(minheap, nxt)
                    added.add(nxt)
        return heapq.heappop(minheap)

核心方法：动态规划

• 定义数组 dp，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n]。
• 由于最小的丑数是 1，因此 dp[1]=1。
• 定义三个指针 $p_2$, $p_3$, $p_5$，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 1。
• 令 $\textit{dp}[i]=\min(\textit{dp}[p_2] \times 2, \textit{dp}[p_3] \times 3, \textit{dp}[p_5] \times 5)$，然后分别比较 dp[i] 和 dp[p_2],dp[p_3], dp[p_5] 是否相等，如果相等则将对应的指针加 1。

时间复杂度：O(n)。需要计算数组 dp 中的 n 个元素，每个元素的计算都可以在 O(1) 的时间内完成。

空间复杂度：O(n)。空间复杂度主要取决于数组 dp 的大小。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        if n == 1: return 1
        dp = [0] * (n+1)
        dp[1] = 1

        p2 = p3 = p5 = 1
        for i in range(2, n+1):
            num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
            dp[i] = min(num2, num3, num5)
            if dp[i] == num2:
                p2 += 1
            if dp[i] == num3:
                p3 += 1
            if dp[i] == num5:
                p5 += 1
        return dp[n]

309，最佳买卖股票含冷冻期，中等

核心方法：动态规划，首先要确定初始状态，总共分为3种，对应的状态转移也是3种。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: return 0

        dp0 = 0              # 手里没股票，没有处于冷冻期
        dp1 = float("-inf")  # 手里没股票，并且处于冷冻期
        dp2 = - prices[0]    # 手里有股票
        
        for i in range(1, len(prices)):
            # 今天没股票，要么就是上次没有买，要么就是上次处于冷冻期
            new_dp0 = max(dp0, dp1)
            # 手里没股票，且处于冷冻期，说明上一次刚卖了
            new_dp1 = dp2 + prices[i]
            # 手里有股票，要么是上一次也有，要么是上一次刚买
            new_dp2 = max(dp2, dp0 - prices[i])
            # 一天不能多次交易，所以需要保存一天当中的记录
            dp0, dp1, dp2 = new_dp0, new_dp1, new_dp2
        return max(dp0, dp1)

887，鸡蛋掉落，困难

核心方法：使用带备忘录的dp函数

定义dp(K ,N)表示给定K，N时，在第i层扔鸡蛋，最坏情况下至少要扔的次数

状态转移：

• 在第i层扔鸡蛋没碎，则K不变，搜索区间为[i+1, n]
• 在第i层扔鸡蛋碎了，则K+1，搜素区间为[1, i-1]
• 二者取最大，因为在最坏情况下，然后还要+1，表示扔了一次

最少要扔几次，表示为 res = min(res, 这次在第i层楼扔的次数（就是上面的结果）)

需要考虑加入带有备忘录的情况，能够减少一定程度上的时间复杂度

时间复杂度：$O(KN^2)$，函数内部循环n次，每个重叠子问题有两个状态，时间复杂度就是O(KN)

空间复杂度：$O(KN)$

python执行结果：超时

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(K, N) -> int:
            # base case
            if K == 1: return N  # 当只有一个鸡蛋时，只能从最顶层开始扔，返回N
            if N == 0: return 0  # 当楼层为0时，不用扔了，返回0
            # 避免重复计算
            if (K, N) in memo:
                return memo[(K, N)]

            res = float('INF')
            # 最坏情况下的最少扔鸡蛋次数，最少体现在min，最多体现在max，取结果大的
            for i in range(1, N + 1):
                # dp(K, N - i)表示没碎，楼层区间为【i+1，N】，鸡蛋数不变
                # dp(K - 1, i - 1)表示碎了，楼层数变为【1，i-1】，鸡蛋数减1
                # 最后+1表示在楼层为i处扔了一次
                res = min(res, max(dp(K, N - i), 
                                   dp(K - 1, i - 1)) + 1)
            # 记入备忘录
            memo[(K, N)] = res
            return res
        
        return dp(K, N)

核心方法：基于二分搜索的动态规划

 很容易知道，K固定时，dp函数一定时随着N的增加而单调递增的 

对于dp(K-1, i-1)和dp(k, N-i)来说，如果固定了K和N，i当作变量，那么前两个函数可以看成是一个单调递增，一个单调递减。这时候求二者的较大值，再求这些最大值之中的最小值，其实就是求这两条直线的交点，也就是折现的最低点。也就是可以使用二分搜索的方式来快速找到这个极值点。

时间复杂度：$O(KNlogN)$

空间复杂度：$O(KN)$

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(K, N):
            # base case
            if K == 1: return N  # 当只有一个鸡蛋时，只能从最顶层开始扔，返回N
            if N == 0: return 0  # 当楼层为0时，不用扔了，返回0
            # 避免重复计算
            if (K, N) in memo:
                return memo[(K, N)]

            res = float('INF')
            lo, hi = 1, N
            while lo <= hi:
                mid = (hi + lo) // 2
                broken = dp(K - 1, mid - 1)
                not_broken = dp(K, N - mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken+1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken+1)

            # 记入备忘录
            memo[(K, N)] = res
            return res
        
        return dp(K, N)

核心方法：定义dp[k][m]为给定k个鸡蛋，最多可以尝试m次，最坏情况下最多能确定测试的楼层数

比如dp[1][7] = 7，现在有1个鸡蛋，允许扔7次，这个状态下最多给你7层楼，使得可以确定从楼层F扔鸡蛋恰好摔不坏。其实最终要求的是状态m，也就是扔鸡蛋的次数。

根据：

• 无论在哪层楼开始扔，鸡蛋要么碎了，要么没碎，碎了的话就测楼下，没碎的话就测楼上
• 无论楼上还是楼下，总的楼层数 = 下面的楼层数 + 1 + 下面的楼层数

状态转移方程为：dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1

其中，dp[k][m-1]表示去楼上，说明鸡蛋没碎，并且仍鸡蛋的次数减1；dp[k-1][m-1]表示去楼下，说明鸡蛋碎了，鸡蛋个数减1，同时扔鸡蛋的次数减一。最后加上当前这个楼层1，就得到了最后的状态转移方程。

时间复杂度：O(KN)

空间复杂度：O(KN)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # dp数组的维度是 (k+1) * (n+1)，这里包含了base case
        dp = [[0] * (N + 1) for _ in range(K+1)]
		# 初始化次数m
        m = 0 
        # 测试条件就是 dp[K][m] == N
        while (dp[K][m] < N):
            # 在新增一次扔鸡蛋的次数下，找到鸡蛋个数与楼层的关系
            m += 1
            for k in range(1, K+1):
                dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
        # 当不满足dp[K][m] < N，最后返回的应该是尝试的次数
        return m

91，解码方法，中等

核心方法：动态规划，定义dp[i]为前i个数字字符串s[1..i]中能够得到的映射方法数

考虑最后一个数字。

• 如果最后一个数字只能映射为一个字母，并且需要保证这个数字不能是零，所以dp[i] = dp[i-1]，这个数字可以被解码为A-I
• 如果最后一个数字被映射为两个字母，并且需要保证前一个位置不能是零，且s[i-1] * 10 + s[i] <= 26。那么dp[i] = dp[i-2]。只有 i > 1时才会有s[i-2]
• 对于dp[0] = 1，可以认为有一种解码方式，接触出来一个空字符串

时间复杂度：O(n)

空间复杂度·：O(n)

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [1] + [0] * n
        for i in range(1, n+1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if s[i-2] != '0' and i > 1 and int(s[i-2:i]) <= 26:
                dp[i] += dp[i-2]
        return dp[n]

当前状态只与前两个状态有关，只用两个变量替换掉dp[i-2]和dp[i-1]

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        first, second, cur = 0, 1, 0
        for i in range(1, n+1):
            cur = 0  # 新的位置下dp[i]应该是0的，所以这里不要忘记将cur置为0
            if s[i-1] != '0':
                cur += second
            if s[i-2] != '0' and i > 1 and int(s[i-2:i]) <= 26:
                cur += first
            first, second = second, cur
        return cur

221，最大正方形，中等

核心方法：动态规划，用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

• 如果该位置的值是 0，则 dp(i,j)=0，因为当前位置不可能在由 1组成的正方形中；
• 如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。
  • dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
• 还需要考虑边界条件。如果 i 和 j 中至少有一个为 0，则以位置 (i,j) 为右下角的最大正方形的边长只能是 1，因此dp(i,j)=1。

时间复杂度：O(mn)

空间复杂度：O(mn)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # 定义dp[i][j]为遍历到[i,j]位置时，只包含1的正方形的边长
        # if matrix[0][0] = 1: dp[0][0] = 1
        
        n, m = len(matrix), len(matrix[0])
        dp = [[0] * m for _ in range(n)]
        
        maxlength = 0
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    maxlength = max(maxlength, dp[i][j])
        return maxlength * maxlength

403，青蛙过河，困难

核心方法：DFS

dfs(pos,step)表示 如果青蛙经过步数为step的跳跃到达位置在pos的石头 它能否跳跃到终点。

时间复杂度：$O(n^2)$

空间复杂度：$O(n^2)$

def canCross(stones: List[int]) -> bool:
    stones_set = set(stones)
    @lru_cache(None)  # 记忆化递归，不需要重复计算
    def dfs(pos,step):
        if pos==stones[-1]: return True  # 终止条件，最后能跳跃到最后一个石头上
        for d in [-1,0,1]:
            if step+d > 0 and pos+step+d in stones_set:
                # step+d 表示只能向前跳
                # pos+step+d 表示落地的位置必须在石头上
                if dfs(pos + step+d, step+d):
                    return True
        # 如果全部情况走完，没有return，那么就返回False
        return False
   	# 初始位置在0，跳跃步数也是0
    pos, step = 0, 0
    return dfs(pos, step)

核心方法：动态规划。定义dp为字典，其中key=stone, value={可以到达stone的跳跃步长组成的集合}。那么能够到达stone等价于dp[stone]非空。

时间复杂度：$O(n^2)$

空间复杂度：O(n)

def canCross(stones: List[int]) -> bool:
    set_stones=set(stones)
    dp = defaultdict(set)
    dp[0]={0}
    for s in stones:
        for step in dp[s]:
            for d in [-1,0,1]:
                if step+d>0 and s+step+d in set_stones:
                    dp[s+step+d].add(step+d)
    return len(dp[stones[-1]])>0

410，分割数组的最大值，困难

核心方法：动态规划，令 dp[i][j] 表示将数组的前 i 个数分割为 j 段所能得到的最大连续子数组和的最小值。

• 进行状态转移时，我们可以枚举 k，其中前 k 个数被分割为 j-1 段，而第 k+1 到第 i 个数为第 j 段。
• 此时的状态转移方程为：dp[i][j] = min{max(f[k][j-1], sub(k+1, i))}
  • f[k][j-1]表示前k个被分成j-1段后，这些子数组的最大和；
  • sub(k+1, i)表示第k+1个数到第i个数的中最大值
• 由于不能分出空的子数组，也就是要求i >= j，也就是不存在前4个数被分为5个组这种不合法情况，可以将这类情况全部初始化为很大的数，反正目标是要求最小值。
• 初始条件：dp[0][0] = 0 表示前0个数（也就是没有数）被分为0组，最小值直接定义为0

时间复杂度：$O(n^2 \times m)$

空间复杂度：$O(n \times m)$

 测试结果：超时，不推荐 

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        # 使用回溯，将数组中数分成m组，然后分别计算每组的最大值，然后维护最小值
        n = len(nums)
        dp = [[10**18] * (m+1) for _ in range(n+1)]
        
        # 提前将子数组中每种子数组的和计算出来
        sub = [0]
        for elem in nums:
            sub.append(sub[-1] + elem)

        dp[0][0] = 0
        for i in range(1, n+1):
            # 这里min(i, m)就保证了取到的j不会大于i
            for j in range(1, min(i ,m)+1):
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i] - sub[k]))

        return dp[n][m]

核心方法，推荐：二分查找+贪心，使......最大值尽可能小，是使用二分搜索的常见问法

二分查找，由于结果值一定出现在数组中的最大值与数组元素和之间。 所以假设中位数(mid)的值就是该结果值，那么遍历数组，前面元素的和如果大于该中位数了，那么表示需要再一次分段。 定义变量 int cnt; cnt就要加1。并且再重新计算数组的和，目的是要保证当前子数组的和不能超过假设的值(mid), 由当前元素值开始往后再次遍历数组，计算出最终的cnt值。 如果cnt的值比m大，就表示分组的太多，也就是代表当初假设的太小了，需要在mid与数组元素和之间继续二分。 如果cnt的值比m小，就表示结果值不是最优的，因为还可以继续多分些组，找到那个最小值。因此需要在数组元素的最大值与mid之间继续二分。 如果cnt的值正好等于m的话，可以合并到cnt的值比m小的的分支一起处理，将当初假设的值继续减小。 通过二分直到查找满足条件的只剩最后一个数字，该数字即为最终的结果

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def check(x: int) -> bool:
            # total表示当前分割子数组的和
            # cnt表示已经分割出的子数组的数量，包括当前子数组
            total, cnt = 0, 1
            for num in nums:
                # 从头判断，当前已遍历元素的和是否大于外部和中值
                if total + num > x:
                    # 如果大于，则将当前元素设定为元素和的头，记录大于的次数
                    # 表示在连续元素和不超过x的情况下，所有元素能分成几组
                    cnt += 1
                    total = num
                else:
                    # 否则就将当前元素添加进总和中
                    total += num
            # 判断大于的次数是否是小于m的
            return cnt <= m

        left = max(nums)
        right = sum(nums)
        while left < right:
            mid = (left + right) // 2
            # 这里的mid是数组nums中，可能的几个元素之和
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left

115，不同的子序列，困难

核心方法：动态规划

• 这里应该是使用二维数组， 字符串s的长度为m，t的长度为n，当m < n时，t不可能存在于s中，直接返回0

• 当m >= n时，从后向前进行遍历。dp[i][j]表示t[j:]在s[i:]出现的个数

• 边界情况：

  • 当 j=n 时，t[j:] 为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0≤i≤m，有 dp[i][n]=1；
  • 当 i=m 且 j<n 时，s[i:] 为空字符串，t[j:]为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 0≤j<n，有 dp[m][j]=0。

• 当 i<m 且 j<n 时，考虑dp[i][j] 的计算：

  • 当 s[i]=t[j] 时，dp[i][j] 由两部分组成：
    • 如果 s[i]和 t[j] 匹配，则考虑 t[j+1:] 作为 s[i+1:] 的子序列，子序列数为dp[i+1][j+1]；
    • 如果 s[i]和 t[j] 不匹配，则考虑 t[j:] 作为 s[i+1:] 的子序列，子序列数为dp[i][j+1]；
    • 因此当 s[i]=t[j] 时，有 dp[i][j]=dp[i+1][j+1]+dp[i+1][j]
  • 当 s[i] != t[j] 时，s[i] 不能和t[j] 匹配，因此只考虑 t[j:] 作为s[i+1:] 的子序列，子序列数为 dp[i+1][j]。
    • 因此当 s[i] != t[j] 时，有dp[i][j]=dp[i+1][j]

时间复杂度：O(mn)

空间复杂度：O(mn)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        if m < n:
            return 0
        
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][n] = 1
        
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if s[i] == t[j]:
                    dp[i][j] = dp[i+1][j] + dp[i+1][j+1]
                else:
                    dp[i][j] = dp[i+1][j]
        return dp[0][0]

279，完全平方数，中等

核心方法：动态规划

定义dp[i]表示和为i的完全平方数的最少数量。这些数必然落在区间 $[1,\sqrt{n}]$，假设当前枚举到 j，那么我们还需要取若干数的平方，构成 $i-j^2$。

所以状态转移方程为：$f[i] = 1+min_{j=1}^{\vert \sqrt i \vert}f[i-j^2]$

需要注意的是，f[0] = 0，其本身并不具备意义，只是为了方便计算，当 $j = \sqrt i$ 时

时间复杂度：$O(n \sqrt n)$，其中 n 为给定的正整数。状态转移方程的时间复杂度为 $O(\sqrt n)$，共需要计算 n 个状态，因此总时间复杂度为 $O(n \sqrt n)$。

空间复杂度：O(n)。我们需要 O(n) 的空间保存状态。

class Solution:
    def numSquares(self, n: int) -> int:
        # dp[i] 表示和为i的完全平方数的最少数量
        dp = [0] + [float('inf')] * n
        for i in range(1, n+1):
            min_v = float('inf')
            j = 1
            while j * j <= i:
                min_v = min(min_v, dp[i-j*j])
                j += 1
            dp[i] = min_v + 1
        return dp[n]

核心方法：四平方和定理

• 四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。
• 当且仅当 $n \neq 4^k \times (8m+7)$时，n 可以被表示为至多三个正整数的平方和。等于时就可以判断为4个整数的平方和

时间复杂度：$O(\sqrt{n})$，其中 n 为给定的正整数。最坏情况下答案为 3，我们需要运行所有的判断，而判断答案是否为 1 的时间复杂度为 O(1)，判断答案是否为 4 的时间复杂度为 $O(\log n)$，剩余判断为 $O(\sqrt n)$，因此总时间复杂度为 $O(\log n + \sqrt n) = O(\sqrt n)$。

空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

class Solution:
    def numSquares(self, n: int) -> int:
        def isSquareNum():
            # 判断是否为完全平方数
            y = int(sqrt(x))
            return y * y == x
        
        def checkAnswer():
            # 判断是否能表示为4^k*(8m+7)
            while x % 4 == 0:
        		x /= 4
            return x % 8 == 7
        
        if isSquareNum(n):
            # 如果当前数就是完全平方数，那么直接返回1
            return 1
        if checkAnswer4(n):
            # 如果当前数能表示为4^k*(8m+7)
            return 4
        # 检查n能够由两个完全平方数组成
        # 其中一个使用挨个遍历的方法，另一个完全平方数使用函数检查
        # 只要有一个满足就直接返回2
        i = 1
        while i*i <= n:
            j = n - i*i
            if isSquareNum(j):
                return 2
            i += 1
        return 3

494，目标和，中等

核心方法：动态规划

记数组的元素和为 $sum$，添加 - 号的元素之和为 $neg$，则其余添加 + 的元素之和为 $sum−neg$，得到的表达式的结果为：$(sum−neg)−neg=sum−2⋅neg = target$

则 $neg = \frac {sum-target}{2}$

上式成立的前提是 $sum-target$ 是非负偶数。若不符合该条件可直接返回 0。问题转化成在数组 nums 中选取若干元素，使得这些元素之和等于 neg，计算选取元素的方案数  这就是标志性0-1背包问题 。我们可以使用动态规划的方法求解。

动态规划方法： dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数。假设数组 nums 的长度为 n，则最终答案为 dp[n][neg]。

当没有任何元素可以选取时，也就是i为0，元素和，也就是j只能是 0，对应的方案数是 1。那么base case就是当 j = 0时，dp[i][j] = 1 ，如果 j > 0 时，dp[0][j]= 0。

• 当 n1 ≤ i ≤ n 时，对于数组 nums 中的第 i 个元素 num（i 的计数从 1 开始），遍历 0 ≤ j ≤ neg，计算 dp[i][j] 的值：
  • 如果 j<num，则不能选 num，此时有 dp[i][j]=dp[i−1][j]；
  • 如果 j≥num，则如果不选 num，方案数是 dp[i−1][j]，如果选 num，方案数是 dp[i−1][j−num]，此时有 dp[i][j] = dp[i−1][j] + dp[i−1][j−num]。

时间复杂度：O(n*neg)

空间复杂度：O(n*neg)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 数组求和
        s = sum(nums)
        # 如果sum - target的值不是偶数，就返回0
        if s - target < 0 or (s - target) % 2 != 0:
            return 0
        n, neg = len(nums), (s - target) // 2
        # 定义dp[i][j]为在前 i 个元素中选取元素，其和为 j 的方案数
        dp = [[0] * (neg + 1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1, n+1):
            # 获取遍历索引对应的数
            num = nums[i-1]
            for j in range(neg+1):
                dp[i][j] = dp[i-1][j]
                if j >= num:
                    # 如果要求的和大于当前数，那么需要补充另外一种情况
                    dp[i][j] += dp[i-1][j-num]
        return dp[n][neg]

从上述动态规划式子上看，当前状态只与上一行状态有关，因此可以进行压缩。内层循环需采用倒序遍历的方式，这种方式保证转移来的是 dp[i−1][] 中的元素值。

时间复杂度：O(n*neg)

空间复杂度：O(neg)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 数组求和
        s = sum(nums)
        if s - target < 0 or (s - target) % 2 != 0:
            return 0
        neg = (s - target) // 2
        dp = [0] * (neg + 1)
        dp[0] = 1
        for num in nums:
            # j 的遍历方式，从后先前遍历，因为首先应计算出dp[j-num]，然后才能计算出dp[j]
            # 因为需要满足j>=num，dp[j-num]才有意义，所以j遍历完num后停止循环
            for j in range(neg, num-1, -1):
                dp[j] += dp[j-num]
        return dp[neg]

338，比特位计数，简单

核心方法：二进制展开，直接统计1

class Solution:
    def countBits(self, n: int) -> List[int]:
        return [bin(i).count('1') for i in range(n+1)]

推荐 核心方法：动态规划

对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x 且 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，此时称 y 为 x 的「最高有效位」。令 z=x−y，显然 0≤z<x，则 bits[x]=bits[z]+1。正整数 y 是 2 的整数次幂，当且仅当 y & (y−1)=0。

显然，0 的「一比特数」为 0。使用 highBit 表示当前的最高有效位，遍历从 1 到 n 的每个正整数 i，进行如下操作：

• 如果 i & (i−1)=0，则令 highBit=i，更新当前的最高有效位。
• i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个整数，因此遍历到 i 时，i−highBit 的「一比特数」已知，令 bits[i]=bits[i−highBit]+1。

class Solution:
    def countBits(self, n: int) -> List[int]:
        bits = [0]
        highBit = 0
        for i in range(1, n + 1):
            if i & (i - 1) == 0:
                highBit = i
            bits.append(bits[i - highBit] + 1)
        return bits

面试题17.24，最大子矩阵，困难

核心方法：动态规划， 最大子序和，二维矩阵转化为一维数组

• 首先要明确的是，最大子序和中，dp[i] = max(dp[i-1]+nums[i], nums[i]) 如果 dp[i-1] 是小于0的，那么加上 nums[i] 后一定比 nums[i] 小
• 二维矩阵转化为一维数组，即从第 i 行累加道第 j 行，也就是每列数据纵向求和，这样 i 到 j 行就合并为一行，这一行就相当于是一个一维数组，在这个数组上求解最大子序和
• 为保证遍历所有的情况，首先使得 i 表示上边界，j 在 (0, n) 行依次取值；然后 i += 1，这样能够完全遍历.
• 在求最大子序和时，如果一个元素将要作为子序列的起始元素，那么它的列就是左上角元素的列，i 为左上元素的行，j 为右下角元素的行，求最大子序和时的索引 k 为右下角元素的列

时间复杂度：$O(mn^2)$

空间复杂度：O(m)

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        # 将二维矩阵转化为一维数组
        n = len(matrix)  # row
        m = len(matrix[0])  # column
        ans = [0] * 4  # 存储结果
        col_sum = [0] * m  # 记录从第i行到第j行的子矩阵中每列的和，列和数组
        max_sum = float('-inf')  # 记录最大和
        for i in range(n):
            # 其中i表示上边界
            for k in range(m):
                # 只要上边界发上了更改，列和数组的每个元素就要重新置0
                col_sum[k] = 0
            for j in range(i, n):
                # j表示下边界
                dp = 0  # 动态维护求和
                for k in range(m):
                    col_sum[k] += matrix[j][k]  # 构建列和数组中的每个元素
                    # 以下与最大子序和相同
                    if dp <= 0:
                        # 原始col_sum加上dp后更小，那么col_sum作为独立起点重新开始计算和
                        dp = col_sum[k]
                        c1 = k  # 从头开始，记录左上边界的列
                    else:
                        # 否则，当前元素应该加到dp中
                        dp += col_sum[k]
                    if dp > max_sum:
                        # 如果当前和大于最大和，就更新最大和，以及四个两个角的坐标
                        max_sum = dp
                        ans[0] = i   # 左上角元素的行
                        ans[1] = c1  # 左上角元素的列
                        ans[2] = j   # 右下角元素的行
                        ans[3] = k   # 右下角元素的列
        return ans

0-1背包问题

416，分割等和子集，中等

• 时间复杂度：O(NC)：这里 N 是数组元素的个数，C 是数组元素的和的一半。
• 空间复杂度：O(NC)。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 定义dp[i][j]为前i个元素中能够取出若干个元素，使得和为j
        s, n = sum(nums), len(nums)
        if s % 2 != 0:
            # 如果这个数组可以满足取出一个子集，使得这个子集的和为数组和的一半
            # 那么这个子集的和一定是偶数
            return False
        s = s // 2
        
        # 初始化dp数组
        dp = [[False] * (s+1) for _ in range(n)]
        for i in range(n):
            # 这里表示的是，前[0..i-1]的数组中，如果什么也不选，和为0，就是True
            dp[i][0] = True
        for i in range(1, n):
            for j in range(1, s+1):
                if j < nums[i]:
                    # 空间小，物品大，不能选当前物品
                    dp[i][j] = dp[i-1][j]
                else:
                    # 空间大，如果不选就是前者，如果选了就是后者，只要有一个是True就行
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
        return dp[n-1][s]

状态压缩的结果：

• 时间复杂度：O(NC)：这里 N 是数组元素的个数，C 是数组元素的和的一半。
• 空间复杂度：O(C)。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 定义dp[i][j]为前i个元素中能够取出若干个元素，使得和为j
        s, n = sum(nums), len(nums)
        if s % 2 != 0:
            # 如果这个数组可以满足取出一个子集，使得这个子集的和为数组和的一半
            # 那么这个子集的和一定是偶数
            return False
        s = s // 2
        
        # 初始化dp数组
        dp = [False] * (s+1)
        dp[0] = True

        for num in nums:
            for j in range(s, num-1, -1):
                # 从后往前遍历，能够保证前面的nums[i]不影响后面的dp[j-nums[i]]
                dp[j] = dp[j] or dp[j - num]
        return dp[s]

474，一和零，中等

核心方法：0-1背包问题

和经典0-1背包问题不同的是，这个问题有两个容量，分别是0和1的数量上限。所以需要三重循环

定义三维数组，dp[i][j][k] 表示在前 i 个字符串中，使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量，题目提供数组长度为l，那么最终结果就是 dp[l][m][n]

边界条件：当 i = 0 表示没有可取的字符串时，对任意 m0 ≤ j ≤ m 和 0 ≤ k ≤ n，都有 dp[i][j][k]=0。

当 1≤i≤l 时，对于 strs 中的第 i 个字符串（计数从 1 开始），首先遍历该字符串得到其中的 0 和 1 的数量，分别记为 zeros 和 ones，然后对于 m0≤j≤m 和 n0≤k≤n，计算 dp[i][j][k] 的值。

当 0 和 1 的容量分别是 j 和 k 时，考虑以下两种情况：

• 如果 j<zeros 或 k<ones，则不能选第 i 个字符串，此时有 dp[i][j][k]=dp[i−1][j][k]；
• 如果 j≥zeros 且 k≥ones，则如果不选第 i 个字符串，有 dp[i][j][k]=dp[i−1][j][k]，如果选第 i 个字符串，有 dp[i][j][k]=dp[i−1][j−zeros][k−ones]+1, dp[i][j][k] 的值应取两项中的最大值。

时间复杂度：O(lmn+L)，其中 l 是数组 strs 的长度，m 和 n 分别是 0 和 1 的容量，L 是数组 strs 中的所有字符串的长度之和。

空间复杂度：O(lmn)

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        def getCount(sin_str):
            # 获取strs每个元素中0和1的数量
            map = {'0': 0, '1': 0}
            for p in sin_str:
                if p in map:
                    map[p] += 1
            return map.values()

        length = len(strs)
        # 创建dp数组
        dp = [[[0] * (n+1) for _ in range(m+1)] for _ in range(length+1)]
        for i in range(1, length + 1):
            zeros, ones = getCount(strs[i-1])
            for j in range(m+1):
                for k in range(n+1):
                    dp[i][j][k] = dp[i-1][j][k]
                    if j >= zeros and k >= ones:
                        # 加1表示选取当前这个字符串，字符串总数要+1
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1)
        return dp[length][m][n]

空间优化（需要注意的几点）

• 去掉遍历第一个维度i的状态
• i 从 0 开始遍历
• j，k 的遍历方式都是逆序遍历，最后遍历到最后的位置是zeros-1，ones-1

时间复杂度：O(lmn+L)，其中 l 是数组 strs 的长度，m 和 n 分别是 0 和 1 的容量，L 是数组 strs 中的所有字符串的长度之和。

空间复杂度：O(mn)

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        def getCount(sin_str):
            # 获取strs每个元素中0和1的数量
            map = {'0': 0, '1': 0}
            for p in sin_str:
                if p in map:
                    map[p] += 1
            return map.values()

        length = len(strs)
        # 创建dp数组
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(length):
            zeros, ones = getCount(strs[i])
            for j in range(m, zeros-1, -1):
                for k in range(n, ones-1, -1):
                    # 加1表示选取当前这个字符串，字符串总数要+1
                    dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones] + 1)
        return dp[m][n]

877，石子游戏，中等

核心方法：动态规划（求解右上三角，行需要倒序遍历，列从行值开始递增遍历）

限制条件：1、数组的长度是偶数；2、数组的元素之和是奇数，没有平局

只有一堆石子，玩家只能取；如果有多堆，那么玩家可以从头或者尾部取。定义dp[i][j] 表示当剩下的石子堆为下标 i 到下标 j 时，即在下标范围 [i, j] 中，当前玩家与另一个玩家的石子数量之差的最大值。

• 只有当 i≤j 时，剩下的石子堆才有意义，因此当 i>j 时，dp[i][j]=0

• 当 i=j 时，只剩下一堆石子，当前玩家只能取走这堆石子，因此对于所有 0≤i<nums.length，都有 dp[i][i]=piles[i]。

• 当 i<j 时，当前玩家可以选择取走 piles[i] 或 piles[j]，然后轮到另一个玩家在剩下的石子堆中取走石子。在两种方案中，当前玩家会选择最优的方案，使得自己的石子数量最大化。因此可以得到如下状态转移方程：dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])

• 最后判断 dp[0][piles.length−1] 的值，如果大于0，则 Alex 的石子数量大于 Lee 的石子数量，因此 Alex 赢得比赛，否则 Lee 赢得比赛。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        for i, pile in enumerate(piles):
            dp[i][i] = pile
        for i in range(n-2, -1, -1):  
            # dp[n-1][n-1] 的位置已经有值了，直接从n-2的位置开始
            for j in range(i + 1, n):
                # j 从 i+1 的位置开始遍历
                dp[i][j] = max(piles[i]-dp[i+1][j], piles[j]-dp[i][j-1])
        return dp[0][n-1] > 0

状态压缩：

• 时间复杂度：$O(n^2)$，其中n是数组的长度。需要计算每个子数组对应的dp的值，共有 $\frac {n(n+1)}{2} $ 个子数组。

• 空间复杂度：O(n)，其中 nn 是数组的长度。空间复杂度取决于额外创建的数组 dp，如果不优化空间，则空间复杂度是 O(n^2)，使用一维数组优化之后空间复杂度可以降至 O(n)。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        length = len(piles)
        dp = [0] * length
        for i, pile in enumerate(piles):
            dp[i] = pile
        for i in range(length - 2, -1, -1):
            for j in range(i + 1, length):
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1])
        return dp[length - 1] > 0

核心方法：数学分析

假设有 n 堆石子，n 是偶数，则每堆石子的下标从 0 到 n-1。根据下标将 n 堆石子分成两组，每组有 n / 2 堆石子，下标为偶数的石子堆属于第一组，下标为奇数的石子堆属于第二组。

作为先手的 Alex 可以在第一次取走石子时就决定取走哪一组的石子，并全程取走同一组的石子。将石子分成两组之后，可以计算出每一组的石子数量，同时知道哪一组的石子数量更多。Alex 只要选择取走数量更多的一组石子即可。因此Alex 总是可以赢得比赛。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True