# 线性DP ## 打家劫舍 这几道题的本质是线性DP中用 $$f\[i]\[k]$$来表示在房子 $$i$$ 是否rob的最大收益。 $$f\[i]\[k] = \begin{cases} \text{not rob:} f\[i]\[0]=\max(f\[i-1]) \ \text{rob:} f\[i]\[1] = f\[i-1]\[0]+\text{nums}\[i] \ \end{cases}$$ 因为 $$f\[i]$$ 只和 $$f\[i-1]$$ 有关，这样的二维DP可以压缩空间到一维，甚至**压缩到两个变量**来解决。 1. [打家劫舍](https://leetcode-cn.com/problems/house-robber/) 2. [打家劫舍 II](https://leetcode-cn.com/problems/house-robber-ii/)：环形结构，分情况讨论就好。 3. [打家劫舍 III](https://leetcode-cn.com/problems/house-robber-iii/)：树上DP，从root开始DFS，每次返回两个变量 4. [删除并获得点数](https://leetcode-cn.com/problems/delete-and-earn/)：把点数放在数组上，转化成打家劫舍I 5. [3n 块披萨](https://leetcode-cn.com/problems/pizza-with-3n-slices/)：延伸，二维$$f\[i]\[j]$$来表示在 $$i$$ 点已经rob了 $$j$$ 个屋子的最大收益。 {% tabs %} {% tab title="I" %} ```python 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金， 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统， 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组， 计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。 ``` ```python def rob(nums): pre = cur = 0 for n in nums: pre, cur = cur, max(cur, pre+n) return cur ``` {% endtab %} {% tab title="II" %} ```python 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。 同时，相邻的房屋装有相互连通的防盗系统， 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组， 计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。 ``` ```python def robLinear(nums): cur, pre = 0, 0 for n in nums: cur, pre = max(pre + n, cur), cur return cur def rob(nums): if len(nums)==1: return nums[0] return max(self.robLinear(nums[:-1]), self.robLinear(nums[1:])) ``` {% endtab %} {% tab title="III" %} ```python 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。 这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。 一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. ``` ```python def helper(root): if not root: return 0, 0 lrob, lskip = helper(root.left) rrob, rskip = helper(root.right) return root.val+lskip+rskip, \ max(lrob, lskip) + max(rrob, rskip) res = helper(root) return max(res) ``` {% endtab %} {% tab title="删除并获得点数" %} ```python 给你一个整数数组 nums ，你可以对它进行一些操作。 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。 之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。 ``` ```python def deleteAndEarn(nums): val = [0 for _ in range(max(nums)+1)] for n in nums: val[n] += n return self.rob(val) ``` {% endtab %} {% tab title="3n 块披萨" %} ```python 给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨： 你挑选 任意 一块披萨。 Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。 Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。 重复上述过程直到没有披萨剩下。 每一块披萨的大小按顺时针方向由循环数组 slices 表示。 请你返回你可以获得的披萨大小总和的最大值。 输入：slices = [1,2,3,4,5,6] 输出：10 解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。 然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。 你获得的披萨总大小为 4 + 6 = 10 。 ``` ```python def rob(nums, N): # return maximum return getting N non-consecutive numbers from nums # f[i][j] = maximum return getting j+1 numbers from 0 to i (inclusive) # f[i][j] = max(f[i-1][j], f[i-2][j-1]+nums[i]) f = [[0]*(N+1) for _ in range(len(nums)+2)] for i, n in enumerate(nums, 2): for j in range(1, N+1): f[i][j] = max(f[i-1][j], f[i-2][j-1]+n) return f[-1][N] def maxSizeSlices(slices): N = (len(slices) + 1) // 3 return max(self.rob(slices[1:], N), self.rob(slices[:-1], N)) ``` {% endtab %} {% endtabs %} ## 粉刷房子 这几道题的本质使用二维DP中$$f\[i]\[k]$$ 来表示把第 $$i$$ 个房子涂成 $$k$$ 色的最小花费。 1. [粉刷房子](https://leetcode-cn.com/problems/paint-house/)： $$k=1, 2, 3.$$ 2. [粉刷房子 II](https://leetcode-cn.com/problems/paint-house-ii/) 3. [粉刷房子 III](https://leetcode-cn.com/problems/paint-house-iii/)：用三维数组来表示把第 $$i$$ 个房子涂成 $$j$$ 色形成 $$k$$ 个街区的最小花费。 {% tabs %} {% tab title="I" %} ```python 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种， 你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。 每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费； costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。 请你计算出粉刷完所有房子最少的花费成本。 输入: [[17,2,17],[16,16,5],[14,3,19]] 输出: 10 解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。   最少花费: 2 + 5 + 3 = 10。 ``` ```python def minCost(costs): n = len(costs) f = [[float('inf')]*3 for _ in range(n+1)] f[0] = [0, 0, 0] for i in range(1, n+1): for k in range(3): f[i][k] = min([costs[i-1][k] + f[i-1][l] for l in range(3) if l!=k]) return min(f[-1]) ``` {% endtab %} {% tab title="II" %} ```python 假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种， 你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。 每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。 例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费； costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。 请你计算出粉刷完所有房子最少的花费成本。 输入: [[1,5,3],[2,9,4]] 输出: 5 解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5;   或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5. ``` ```python def minCostII(costs): n, m = len(costs), len(costs[0]) if m == 1 :return min([c[0] for c in costs]) f = [[float('inf')]*m for _ in range(n+1)] f[0] = [0]*m for i in range(1, n+1): for k in range(m): f[i][k] = min([f[i-1][l] for l in range(m) if l!=k]) f[i][k] += costs[i-1][k] return min(f[-1]) ``` {% endtab %} {% tab title="III" %} ```python 在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一 （颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新涂色。 我们将连续相同颜色尽可能多的房子称为一个街区。 比方说 houses = [1,2,2,3,3,2,1,1] ， 它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。 给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中： houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。 cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。 请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后， 恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。 输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3 输出：9 解释：房子涂色方案为 [1,2,2,1,1] 此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。 涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。 ``` ```python def minCost(houses, cost, m, n, target): f = [[[float('inf')]*(target+1) for _ in range(n+1)] for _ in range(m+1)] for i in range(m+1): for j in range(n+1): if i==0 or j==0: f[i][j][0] = 0 # case 1: different color, new block # case 2: same color, no new block # if previously colored, then j needs be same color as before # if not colored, then there is extra cost to color for i in range(1, m+1): color = houses[i-1] for j in range(1, n+1): if color and j!=color: continue for k in range(1, min(target, i)+1): f[i][j][k] = min([f[i-1][p][k-1] for p in range(1, n+1) if p!=j]) f[i][j][k] = min(f[i][j][k], f[i-1][j][k]) if not color: f[i][j][k] += cost[i-1][j-1] res = min(f[-1][j][-1] for j in range(1, n+1)) return -1 if res==float('inf') else res ``` {% endtab %} {% endtabs %} ## 买卖股票 这几道的本质是用二维DP中$$f\[i]\[k]$$ 来表示在 $$i$$ 天执行$$k$$动作后的最大收益。因为股票要买了以后才能卖，而且在延伸题中对交易次数的限制，或者冷冻期的限制，我们可能要拓展状态 $$k$$ 或者引入第三个维度 $$f\[i]\[k]\[m]$$ 来记录已经完成了 $$m$$ 个交易。 由于在转移方程中 $$f\[i]$$ 只与前一天 $$f\[i-1]$$有关，我们可以用滚动数组来节约第一个时间维度。 1. [买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)：总共只能买卖各一次 2. [买卖股票的最佳时机 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)：每天可以买或卖一次，必须在再次购买前出售，可以完成无限笔 3. [买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)：同二，最多完成两笔交易 4. [买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)：同三，最多完成K笔交易 5. [最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)：同二，卖出之后锁定一天 6. [买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)：同二，每次交易有手续费fee {% tabs %} {% tab title="I" %} ```python 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。 设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出， 最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 ``` ```python def maxProfit(prices): sell, buy = 0, float('-inf') for p in prices: buy = max(buy, -p) sell = max(sell, buy+p) return sell # 压缩空间前： def maxProfit(prices): f = [[0]*2 for _ in range(len(prices)+1)] f[0][1] = float('-inf') for i, p in enumerate(prices, 1): f[i][0] = max(f[i-1][0], f[i-1][1]+p) f[i][1] = max(f[i-1][1], -p) return f[-1][0] # 另一种解法：转化成最大子串 def maxSubarray(nums): res = pre = 0 for n in nums: pre = max(pre+n, n) res = max(res, pre) return res def maxProfit(prices): diff = [] pre = prices[0] for p in prices[1:]: diff.append(p-pre) pre = p return self.maxSubarray(diff) ``` {% endtab %} {% tab title="II" %} ```python 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 ``` ```python def maxProfit(prices): sell, buy = 0, float('-inf') for p in prices: sell, buy = max(buy+p, sell), max(buy, sell-p) return sell # 压缩空间之前 def maxProfit(prices): f = [[0]*2 for _ in range(len(prices)+1)] f[0][1] = float('-inf') for i, p in enumerate(prices, 1): f[i][0] = max(f[i-1][0], f[i-1][1]+p) f[i][1] = max(f[i-1][1], f[i-1][0]-p) return f[-1][0] ``` {% endtab %} {% tab title="III" %} ```python 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出， 这笔交易所能获得利润 = 3-0 = 3 。   随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出， 这笔交易所能获得利润 = 4-1 = 3 。 ``` ```python def maxProfit(prices): buy1 = buy2 = float('-inf') sell1 = sell2 = 0 for p in prices: buy1 = max(buy1, -p) sell1 = max(sell1, buy1+p) buy2 = max(buy2, sell1-p) sell2 = max(sell2, buy2+p) return sell2 # 压缩空间之前 def maxProfit(self, prices: List[int]) -> int: kmax = 2 # f[i][j][k] is the maximum revenue on ith day # j=0: no stock, j=1: have stock # k: number of transactions so far f = [[[0]*(kmax+1) for _ in range(2)] for _ in range(len(prices)+1)] for k in range(1, kmax+1): f[0][1][k] = float('-inf') for i, p in enumerate(prices, 1): for k in range(1, kmax+1): f[i][0][k] = max(f[i-1][0][k], f[i-1][1][k]+p) f[i][1][k] = max(f[i-1][1][k], f[i-1][0][k-1]-p) return f[-1][0][-1] ``` {% endtab %} {% tab title="IV" %} ```python 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出， 这笔交易所能获得利润 = 4-2 = 2 。 ``` ```python def maxProfit(k, prices): kmax = k buy = [float('-inf') for _ in range(kmax+1)] sell = [0 for _ in range(kmax+1)] for p in prices: for k in range(1, kmax+1): buy[k] = max(buy[k], sell[k-1]-p) sell[k] = max(sell[k], buy[k] + p) return sell[-1] # 压缩空间前 def maxProfit(k, prices): # f[i][j][k] is the maximum revenue on ith day # j=0: no stock, j=1: have stock # k: number of transactions so far kmax = k f = [[[0]*(kmax+1) for _ in range(2)] for _ in range(len(prices)+1)] for k in range(1, kmax+1): f[0][1][k] = float('-inf') for i, p in enumerate(prices, 1): for k in range(1, kmax+1): f[i][0][k] = max(f[i-1][0][k], f[i-1][1][k]+p) f[i][1][k] = max(f[i-1][1][k], f[i-1][0][k-1]-p) return f[-1][0][-1] ``` {% endtab %} {% tab title="含冷冻期" %} ```python 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​ 设计一个算法计算出最大利润。 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] ``` ```python def maxProfit(prices): sell, buy, locked = 0, float('-inf'), 0 for p in prices: sell, buy, locked = max(sell, buy+p), max(buy, locked-p), sell return max(sell, locked) # 压缩空间前 def maxProfit(self, prices: List[int]) -> int: # f[i][j] is the maximum profit on day i # j=0: sold, unlocked # j=1: buy # j=2: sell, locked f = [[0]*3 for _ in range(len(prices)+1)] f[0][1] = float('-inf') for i, p in enumerate(prices, 1): f[i][0] = max(f[i-1][0], f[i-1][2]) f[i][1] = max(f[i-1][1], f[i-1][0]-p) f[i][2] = f[i-1][1]+p return max(f[-1][0], f[-1][2]) ``` {% endtab %} {% tab title="含手续费" %} ```python 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ； 非负整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8 解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8. ``` ```python def maxProfit(prices, fee): sell, buy = 0, float('-inf') for p in prices: sell, buy = max(buy+p-fee, sell), max(buy, sell-p) return sell # 压缩空间前 def maxProfit(prices, fee): f = [[0]*2 for _ in range(len(prices)+1)] f[0][1] = float('-inf') for i, p in enumerate(prices, 1): f[i][0] = max(f[i-1][0], f[i-1][1]+p-fee) f[i][1] = max(f[i-1][1], f[i-1][0]-p) return f[-1][0] ``` {% endtab %} {% endtabs %} ## 字符串匹配 这里把单串线性动态规划留到专题：子串/子序列最值。 下面这几道题是经典的双串问题。本质是用 $$f\[i, j]$$ 来表示第一串考虑\[0, ..i]，第二串考虑\[0, ...j]的答案。转移方程一般为： $$f\[i, j] = g(f\[i-1]\[j] + \text{cost}\_1, f\[i]\[j-1]+ \text{cost}\_2, f\[i-1]\[j-1]+ \text{cost}\_3).$$ 方程中一直增加的是 $$i$$ 和 $$j$$ ，所以迭代顺序$$i$$ 和 $$j$$从小到大就好了。 1. [最长公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/)（LCS）：最长的公共subsequence 2. [最长公共子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)（LCSubarray）：最长的公共subarray 3. [两个字符串的最小ASCII删除和](https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/)（ASCII） 4. [编辑距离](https://leetcode-cn.com/problems/edit-distance/)（Edit Distance） 5. [通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/)（Wildcard Matching） 6. [正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching/)（Regex Matching） 7. [不同的子序列](https://leetcode-cn.com/problems/distinct-subsequences/)（Distinct) 8. [扰乱字符串](https://leetcode-cn.com/problems/scramble-string/)（Scramble）：$$f\[i, j, l]$$ = 从 $$s\_1\[i]$$ 和 $$s\_2\[j]$$ 开始的长度为 $$l$$ 的子串是否match。match的可能有两种，所以枚举中点 $$w$$ {% tabs %} {% tab title="LCS" %} ```python 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。 如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串： 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符 （也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。 输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。 ``` ```python def longestCommonSubsequence(text1, text2): m, n = len(text1), len(text2) f = [[0]*(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]: f[i][j] = f[i-1][j-1]+1 else: f[i][j] = max(f[i][j-1], f[i-1][j]) return f[-1][-1] ``` {% endtab %} {% tab title="LCSubarry" %} ```python 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。 ``` ```python def findLength(text1, text2): m, n = len(text1), len(text2) f = [[0]*(n+1) for _ in range(m+1)] res = 0 for i in range(1, m+1): for j in range(1, n+1): if text1[i-1]==text2[j-1]: f[i][j] = f[i-1][j-1] + 1 res = max(res, f[i][j]) return res ``` {% endtab %} {% tab title="ASCII" %} ```python 给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。 输入: s1 = "sea", s2 = "eat" 输出: 231 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。 在 "eat" 中删除 "t" 并将 116 加入总和。 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。 ``` ```python def minimumDeleteSum(self, s1: str, s2: str) -> int: if not s1 or not s2: return 0 # f[i][j] = min(f[i][j-1]+a(sj), f[i-1][j]+a(si)) if si!=sj # f[i][j] = f[i-1][j-1] if si==sj ni, nj = len(s1), len(s2) f = [[0]*(nj+1) for _ in range(ni+1)] for i in range(ni-1, -1, -1): f[i][nj] = f[i+1][nj] + ord(s1[i]) for j in range(nj-1, -1, -1): f[ni][j] = f[ni][j+1] + ord(s2[j]) for i in range(ni-1, -1, -1): for j in range(nj-1, -1, -1): si, sj = s1[i], s2[j] if si==sj: f[i][j] = f[i+1][j+1] else: c1 = f[i][j+1] + ord(sj) c2 = f[i+1][j] + ord(si) f[i][j] = min(c1, c2) return f[0][0] ``` {% endtab %} {% tab title="Edit" %} ```python 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： - 插入一个字符 - 删除一个字符 - 替换一个字符 输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') ``` ```python def minDistance(word1, word2): n1, n2 = len(word1), len(word2) f = [[0]*(n2+1) for _ in range(n1+1)] for i in range(n1+1): for j in range(n2+1): if i==0 or j==0: f[i][j] = i + j elif word1[i-1]==word2[j-1]: f[i][j] = f[i-1][j-1] else: f[i][j] = min(f[i-1][j-1], f[i][j-1], f[i-1][j]) + 1 return f[-1][-1] ``` {% endtab %} {% tab title="Wildcard" %} ```python 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。 - '?' 可以匹配任何单个字符。 - '*' 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。 说明: - s 可能为空，且只包含从 a-z 的小写字母。 - p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 ``` ```python def isMatch(s, p): m, n = len(s), len(p) f = [[False]*(n+1) for _ in range(m+1)] f[0][0] = True for i in range(1, n+1): f[0][i] = f[0][i-1] and p[i-1]=="*" for i in range(1, m+1): for j in range(1, n+1): if s[i-1]==p[j-1] or p[j-1]=="?": f[i][j] = f[i-1][j-1] if p[j-1]=="*": f[i][j] = f[i][j-1] or f[i-1][j] return f[-1][-1] # Memoization def isMatch(s, p): @cache def helper(i, j): if i==len(s): return j==len(p) or (p[j]=="*" and helper(i, j+1)) if j==len(p): return False if p[j]=="*": # case1: "*" = empty string # case2: "*" = sequence res = helper(i, j+1) or helper(i+1, j) else: first = (p[j] in ["?", s[i]]) res = first and helper(i+1, j+1) return res return helper(0, 0) ``` {% endtab %} {% tab title="Regex" %} ```python 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 - '.' 匹配任意单个字符 - '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 输入：s = "aa" p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。 ``` ```python def isMatch(s, p): def matches(i, j): if i==0: return False return p[j-1] in [s[i-1], '.'] m, n = len(s), len(p) f = [[False for _ in range(n+1)] for _ in range(m+1)] f[0][0] = True for i in range(m+1): for j in range(1, n+1): if p[j-1] == "*": f[i][j] |= f[i][j-2] if matches(i, j-1): f[i][j] |= f[i-1][j] elif matches(i, j): f[i][j] |= f[i-1][j-1] return f[-1][-1] ``` {% endtab %} {% tab title="Distinct" %} ```python 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰 剩余字符相对位置所组成的新字符串。 （例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是） 题目数据保证答案符合 32 位带符号整数范围。 输入：s = "rabbbit", t = "rabbit" 输出：3 解释： 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。 (上箭头符号 ^ 表示选取的字母) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^ ``` ```python def numDistinct(s, t): m, n = len(s), len(t) f = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): f[i][0] = 1 for i in range(1, m+1): for j in range(1, n+1): f[i][j] = f[i-1][j] if s[i-1]==t[j-1]: f[i][j] += f[i-1][j-1] return f[-1][-1] # Memoization def numDistinct(s, t): @cache def dfs(i, j): if i==len(s) or j==len(t): return 1 if j==len(t) else 0 # done! res = 0 if s[i]==t[j]: res += dfs(i+1, j+1) # match! use char in s res += dfs(i+1, j) # skip char in s return res return dfs(0, 0) ``` {% endtab %} {% tab title="Scarmble" %} ```python 使用下面描述的算法可以扰乱字符串 s 得到字符串 t ： - 如果字符串的长度为 1 ，算法停止 - 如果字符串的长度 > 1 ，执行下述步骤： * 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ， 则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。 * 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。 即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。 * 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。 如果是，返回 true ；否则，返回 false 。 输入：s1 = "great", s2 = "rgeat" 输出：true 解释：s1 上可能发生的一种情形是： "great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串 "gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」 "gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割 "g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」 "r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t" "r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」 算法终止，结果字符串和 s2 相同，都是 "rgeat" 这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/scramble-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ``` ```python def isScramble(s1, s2): if len(s1)!=len(s2): return False n = len(s1) f = [[[False]*(n+1) for _ in range(n)] for _ in range(n)] for l in range(1, n+1): for i in range(n-l+1): for j in range(n-l+1): if l==1: f[i][j][1] = s1[i]==s2[j] continue for w in range(1, l): f[i][j][l] |= f[i][j][w] and f[i+w][j+w][l-w] if f[i][j][l]: break f[i][j][l] |= f[i][j+l-w][w] and f[i+w][j][l-w] if f[i][j][l]: break return f[0][0][-1] # Memoization def isScramble(s1, s2): n = len(s1) @cache def helper(i, j, l): if l==1: return s1[i]==s2[j] for w in range(1, l): if (helper(i, j, w) and helper(i+w, j+w, l-w)) or \ (helper(i, j+l-w, w) and helper(i+w, j, l-w)): return True return False return helper(0, 0, n) ``` {% endtab %} {% endtabs %} ## 跳跃游戏 在每一个点的可能跳到的目的地有所限制，求可行解或者最优解（最少步数，最大分数等）。用动态规划或者图的搜索方法DFS/BFS求解。如果需要优化，基本上是用贪心来加速（I，II，VI）。 1. [跳跃游戏](https://leetcode-cn.com/problems/jump-game/)：能否跳到最后点。 2. [跳跃游戏 II](https://leetcode-cn.com/problems/jump-game-ii/)：跳到最后点的最少步数 3. [跳跃游戏 III](https://leetcode-cn.com/problems/jump-game-iii/)：能否从start可以前后跳跃至end。DFS细节： 1. 为什么要vis数组。因为可能有cycle。 2. 为什么DFS**不一定**需要回溯，因为没有死胡同。事实上，终点就是死胡同：因为arr\[终点]=0 4. [跳跃游戏 IV](https://leetcode-cn.com/problems/jump-game-iv/)：与III类似用BFS+vis标记 5. [跳跃游戏 V](https://leetcode-cn.com/problems/jump-game-v/)： $$\[i-D, i+D]$$ 跳跃区间，从高处向下跳的最多步数。DP解法需要先把问题排序。 6. [跳跃游戏 VI](https://leetcode-cn.com/problems/jump-game-vi/)： $$\[i+1, i+\max]$$ 跳跃区间，得分最高的路径。用大顶堆贪心优化可以减少时间。 7. [跳跃游戏 VII](https://leetcode-cn.com/problems/jump-game-vii/)： $$\[i+\min, i+\max]$$ 跳跃区间，能否跳到最后点。难点是用O(n)来更新能到达的地点，用far来标记能到达的最远距离 8. [青蛙过河](https://leetcode-cn.com/problems/frog-jump/)： $$\[\text{step}-1, \text{step}, \text{step}+1]$$ 跳跃区间，能否跳到最后点。 9. [最少侧跳次数](https://leetcode-cn.com/problems/minimum-sideway-jumps/)：递归DP {% tabs %} {% tab title="I" %} ```python 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 ``` ```python def canJump(nums): far = 0 for i, step in enumerate(nums): if far < i: return False far = max(far, i+step) return True ``` {% endtab %} {% tab title="II" %} ```python 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 ``` ```python def jump(nums): far = maxPos = res = 0 for i, step in enumerate(nums[:-1]): far = max(far, i+step) if i==maxPos: maxPos = far res += 1 return res # DP def jump(nums): f = [float('inf') for _ in range(len(nums))] f[0] = 0 for i in range(len(nums)): for j in range(i): if nums[j]+j >= i: f[i] = min(f[i], f[j]+1) return f[-1] ``` {% endtab %} {% tab title="III" %} ```python 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。 当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。 注意，不管是什么情况下，你都无法跳到数组之外。 输入：arr = [4,2,3,0,3,1,2], start = 5 输出：true 解释： 到达值为 0 的下标 3 有以下可能方案： 下标 5 -> 下标 4 -> 下标 1 -> 下标 3 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 ``` ```python # BFS def canReach(arr, start): queue = [start] vis = set([start]) while queue: i = queue.pop(0) if arr[i] == 0: return True for j in [i-arr[i], i+arr[i]]: if not 0<=j= 0 j 满足：arr[i] == arr[j] 且 i != j 请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。 注意：任何时候你都不能跳到数组外面。 输入：arr = [100,-23,-23,404,100,23,23,23,3,404] 输出：3 解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。 下标 9 为数组的最后一个元素的下标。 ``` ```python def minJumps(arr): mval = defaultdict(list) for i, n in enumerate(arr): mval[n].append(i) start, final = 0, len(arr)-1 queue = [(start, arr[start])] res = 0 vis = set([start]) while queue: for _ in range(len(queue)): i, val = queue.pop(0) if i==final: return res for j in [i-1, i+1] + mval[val]: if not 0<=j= 0 且 0 < x <= d 。 除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ， 其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。 你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。 请注意，任何时刻你都不能跳到数组的外面。 输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2 输出：4 解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。 注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。 你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。 类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处 ``` ```python def maxJumps(A, d): f = [1 for _ in range(len(A))] for _, i in sorted([a, i] for i, a in enumerate(A)): for di in [-1, 1]: for j in range(i+di, i+d*di+di, di): if not (0<=jk: heapq.heappop(queue) res = -queue[0][0] + nums[i] heapq.heappush(queue, (-res, i)) return res ``` {% endtab %} {% tab title="VII" %} ```python 给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。 一开始，你在下标 0 处，且该位置的值一定为 '0' 。 当同时满足如下条件时，你可以从下标 i 移动到下标 j 处： i + minJump <= j <= min(i + maxJump, s.length - 1) 且 s[j] == '0'. 如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。 输入：s = "011010", minJump = 2, maxJump = 3 输出：true 解释： 第一步，从下标 0 移动到下标 3 。 第二步，从下标 3 移动到下标 5 。 ``` ```python def canReach(s, minJump, maxJump): v = [i for i in range(len(s)) if s[i]=="0"] if v[-1] != len(s)-1: return False n = len(v) f = [False for _ in range(n)] f[0] = True far = 0 for i in range(n): if not f[i]: continue while far < n and v[far] <= v[i]+maxJump: if v[far]>=v[i]+minJump: f[far] = True far += 1 return f[-1] # TLE def canReach(s, minJump, maxJump): n = len(s) f = [False for _ in range(n)] f[0] = True for j in range(n): if s[j]!="0": continue for i in range(j): if s[i]!="0": continue if not f[i]: continue if i+minJump <= j <= min(i+maxJump, n-1): f[j] = True break return f[-1] ``` {% endtab %} {% tab title="青蛙过河" %} ```python 一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子 （也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。 给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。 开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位 （即只能从单元格 1 跳至单元格 2 ）。 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。 输入：stones = [0,1,3,5,6,8,12,17] 输出：true 解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。 ``` ```python def canCross(stones): n = len(stones) f = [[False]*n for _ in range(n)] f[0][1] = True for i in range(1, n): for j in range(i): step = stones[i] - stones[j] if step>=n or not f[j][step]: continue f[i][step] = True if step-1>=0: f[i][step-1] = True if step+1