LeetCode Packet 1
44. Wildcard Matching
各方面都更像 0010 - Regular Expression Matching II ，前者是正则匹配，后者则是一般 shell 上文件名的匹配，而且后者（也就是本题）的 DP 实现可以把时间和空间性能很好地结合在一起。
把模式串的遍历放在外循环，唯一需要仔细考虑下的就是每一轮 DP 的初始化：
- 第一轮的 DP，$\text{dp}[0] = \text{true}$ ，也就是空串匹配空串，其他位置是非空文本串匹配空模式串，显然全都是 $\text{false}$ ；
- 第二轮及之后的 DP，如果对应位置是
*符号，$\text{dp}[0]$ 就等于前一轮的 $\text{dp}[0]$ ，否则就排除了模式串前缀全是星符号的情况，就一定是 $\text{false}$
def solve(s: str, p: str) -> bool:
dp = [False] * (len(s)+1)
# j = 0
dp[0] = True
for j in range(1, len(p)+1):
if p[j-1] == '*':
for i in range(1, len(s)+1):
dp[i] = dp[i-1] or dp[i]
elif p[j-1] == '?':
prev1 = dp[0]
dp[0] = False
for i in range(1, len(s)+1):
dp[i], prev1 = prev1, dp[i]
else:
prev1 = dp[0]
dp[0] = False
for i in range(1, len(s)+1):
if s[i-1] == p[j-1]:
dp[i], prev1 = prev1, dp[i]
else:
prev1 = dp[i]
dp[i] = False
return dp[-1]
和一个直接使用 fnmatch.fnamtch 的运行时间一致。
403. Frog Jump
一个最优时间复杂度为 $O(n^2)$ 的动态规划的题目，有点儿无语了。
分为自顶向下（渐进递归），和自底向上两个实现方法，这种时间复杂度 $O(n^2)$ 的题目实在没什么好讲的。
使用哈希表而不是二维数组的好处是可以直接把值放进表里，而不需要额外的值的哈希表来查找值对应的索引1
from typing import List
from collections import defaultdict
def solve(stones: List[int]) -> bool:
if stones[1] != 1:
return False
if len(stones) == 2:
return True
k_candicates = defaultdict(set, {1: [1]})
for v in stones[1:-1]:
for k in k_candicates.pop(v, []):
if abs(v+k-stones[-1]) <= 1:
return True
if k > 1:
k_candicates[v+k-1].add(k-1)
k_candicates[v+k].add(k)
k_candicates[v+k+1].add(k+1)
return False
时间复杂度：$O(n^2)$ 。
运行时间：164 ms (beats 74.64%)，内存占用：17.6 MB (beats 98.33%)
2498. Frog Jump II
从头跳到尾，跳过去再跳回来，每次不能跳跳过的石头，每一跳的最大值即为整个路径的值，求最小的路径值。
既然是跳过去再跳回来，那么可以在一遍扫描的时候直接找两条最短的路径，由于没有任何跳跃的限制，因此不存在某一跳较大但因此其他跳较小的情况，因为总是可以通过较小的跳跳到该位置，这就可以使用贪心地思想，直接寻找最小的下一跳。
可以直接从序号一开始，两两一组，1跳3，2跳4，如此，这就是最小的路径值的跳法儿。
def solve(stones: List[int]) -> int:
n = len(stones)
if n <= 2:
return stones[-1]-stones[0]
for i in range(3, n-1, 2):
ans = max(ans, stones[i]-stones[i-2], stones[i+1]-stones[i-1])
if (n-1) % 2 == 1:
ans = max(ans, stones[-1]-stones[-3])
return ans
时间复杂度 $O(n)$ 。
运行时间：558 ms (beats 98.8%)，内存占用：31.12 MB (beats 44.23%) 。
必须吐槽下，这个完全是 $O(1)$ 的内存使用内存占用居然不是最好的，因为还有处理过程中直接修改输入数组（弹出元素）的情况。
可以用一种混合地写法看起来更简洁：
def solve(stones: List[int]) -> int:
n = len(stones)
ans = stones[1]-stones[0]
for i in range(0, n-2):
ans = max(ans, stones[i+2]-stones[i])
return ans
但由于 ans 的比较次数多了一倍，性能要稍差些。
运行时间：580 ms
62. Unique Paths
非常常见的动态规划的一类题目，利用计算过的更小规模的值计算后面更大的值。
from functools import cache
@cache
def solve(m: int, n: int) -> int:
if m == 1:
return 1
return sum([solve(m-1, i) for i in range(1, n+1)])
时间复杂度 $O(mn)$ 。
运行时间：46 ms (beats 44.10%)，内存占用：16.4 MB (beats 48.70%) 。
如果只是单次求解，可以把空间规模缩减到 $O(\min(m,n))$ ，就像之前 Wildcard Matching 那样，但这意义不大，特别地对于这道题目，记忆空间的缩减也有数学上的解释，就是当前位置值就是取杨辉三角上一行的前一个位置和上一行的同一个位置之和。
而实际上杨辉三角展示得是就是组合数的代数性质，可以直接求组合数，空间占用就变成了 $O(1)$。
从组合的观点看，因为我们的走法儿每一步是不受前面步的影响，唯一限制就是横向要走 $m-1$ 步，纵向要走 $n-1$ 步，因此总地组合空间就是从 $m-1+n-1$ 步中选取 $m-1$ 或 $n-1$ 步：$\displaystyle C_{m+n-2}^{m-1}$ 。
from math import comb
def solve(m: int, n: int) -> int:
return comb(m+n-2, m-1)
具体时间复杂度由组合数的计算方法决定，使用原始地算数运算大概有 $O(\min(m,n))$ 。
运行时间：39 ms (beats 77.42%)，内存占用：16.1 MB (beats 99.75%) 。
63. Unique Paths II
出题者使用了“绊脚石”排除了简单的数学解法，但是递归 DP 仍然有效，只要排除石头挡路的情况。
from typing import List
from functools import cache
def solve(obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
@cache
def dp(i: int, j: int) -> int:
if obstacleGrid[i-1][j-1]:
return 0
if i == 1 and j == 1:
return 1
if i == 1:
return dp(i, j-1)
elif j == 1:
return dp(i-1, j)
else:
return dp(i, j-1) + dp(i-1, j)
return dp(m, n)
时间复杂度 $O(nm)$
运行时间：56 ms (beats 23.68%)，内存占用：16.8 MB (beats 7.1%, ~100%) 。
虽然好像时间内存排名不是很高，但是实际数据上差别不大，和前面一样也可以缩减到 $O(\min(m,n)$ 的内存占用，不赘述了。
64. Minimum Path Sum
和独特路径完全一样。
from typing import List
from functools import cache
def solve(grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
@cache
def dp(i: int, j: int) -> int:
if i == 1 and j == 1:
return grid[0][0]
elif i == 1:
return dp(i, j-1) + grid[i-1][j-1]
elif j == 1:
return dp(i-1, j) + grid[i-1][j-1]
else:
return min(dp(i, j-1), dp(i-1, j)) + grid[i-1][j-1]
return dp(m, n)
97. Interleaving String
交错两个字符串 $s_1$ 和 $s_2$ ，看是否等于第三个字符串 $s_3$ 。
这个成立的渐进式条件是，$s_1$ 、 $s_2$ 的前缀同样可以交错成 $s_3$ 的某个前缀。
因此可以从前缀长度是 $0$ 的空子串开始，判断两种情况：
- $s_1$ 前缀的下一个字符是否等于 $s_3$ 前缀的下一个字符；
- $s_2$ 前缀的下一个字符是否等于 $s_3$ 前缀的下一个字符
这也分别构成两种情况的递归，递归的参数应该是匹配的 $s_1$ 、 $s_2$ 和 $s_3$ 的前缀长度 $i, j, k$ 。
但实际上 $k$ 是可以被省略的，当匹配发生时，那么 $k=i+j$ 。
另外有两个快速失败的优化：
- 长度不等，快速失败
- 字符和每个字符的次数（multiset）不等，快速失败2
递归版本：
from collections import Counter
def solve(s1: str, s2: str, s3: str) -> bool:
n1 = len(s1)
n2 = len(s2)
n3 = len(s3)
if n1+n2 != n3:
return False
if Counter(s1) + Counter(s2) != Counter(s3):
return False
mem = [[True] * (n2+1) for _ in range(n1+1)]
def recur(i: int, j: int) -> bool:
if i+j == n3:
return True
if not mem[i][j]:
return False
if i < n1 and s1[i] == s3[i+j] and recur(i+1, j):
return True
if j < n2 and s2[j] == s3[i+j] and recur(i, j+1):
return True
mem[i][j] = False
return False
return recur(0, 0)
以 $i,j$ 某一个参数为外循环，而不是同时尝试增加 $i,j$ ，这样就得到了迭代的版本。迭代版本有一个好处是可以压缩记忆的内存从 $O(n^2)$ 到 $O(n)$ ，因为记忆只涉及前一行和当前行（mem[i-1][j], mem[i][j-1]）。
迭代版本：
def solve(s1: str, s2: str, s3: str) -> bool:
n1 = len(s1)
n2 = len(s2)
n3 = len(s3)
if n1 + n2 != n3:
return False
if Counter(s1) + Counter(s2) != Counter(s3):
return False
mem = [False] * (n2 + 1)
mem[0] = True
for j in range(1, n2 + 1):
if s2[j-1] == s3[j-1]:
mem[j] = True
else:
break
for i in range(1, n1 + 1):
if not mem[0] or s1[i - 1] != s3[i - 1]:
mem[0] = False
for j in range(1, n2 + 1):
if (
mem[j]
and s1[i - 1] == s3[i + j - 1]
or mem[j - 1]
and s2[j - 1] == s3[i + j - 1]
):
mem[j] = True
else:
mem[j] = False
return mem[n2]
需要特别注意下 $s_1$ 是空串的情况。
213. House Robber II
这道题建立在 198. House Robber 的基础上，假设我们已经有了一个它的解3：
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(dp[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
return dp[n-1]
由于 0 <= nums[i] <= 400 的数据特点，可以通过滚动变量简化为：
def rob(self, nums: List[int]) -> int:
dp0, dp1 = 0, 0
for v in nums:
dp0, dp1 = dp1, max(dp1, dp0+v)
return dp1
而 House Robber II 的困难在于并不容易直接想到 House 首尾相接成环到底意味着什么。
相比之下，可以这么考虑，只要求一个最大值，要求首尾不能同时被取到。
那么只有两种情况：要么首部一定不会被取到、要么尾部一定不会被取到，也就是 rob(nums[1:]) 和 rob(nums[:-1]) ，另外考虑到特殊的长度为 $1$ 的情况，就得到了最终的结果。
def rob(self, nums: List[int]) -> int:
def rob0(nums):
dp0, dp1 = 0, 0
for v in nums:
dp0, dp1 = dp1, max(dp1, dp0+v)
return dp1
return max(
rob0(nums[1:]),
rob0(nums[:-1]),
nums[0]
)
221. Maximal Square
这个题从名字上看就像是前面 0085 - Maximal Rectangle ，区别是这里是 “Square” ，正方形，是进一步特定了的矩形，显然 0085 - Maximal Rectangle 的解题的两种思路都可以直接应用在这里，只需要将最大矩形的形状限制在正方形即可。
这里要介绍的是特别针对正方形的限制的一种 DP 思路：
正方形的好处是它是一个中心对称的几何图形，大的正方形可以通过小的正方形拓展而来。
使用几何“缩放”的形式实现问题规模的递增，对于一个坐标为 $(i, j)$ 的点来说，如果它被“填充”了，并且其余三个位置：$(i,j-1), (i-1,j), (i-1,j-1)$ 也都被填充了，那么这就是一个 2x2 的正方形，如果其中任一一个位置未被填充，那么这就是一个 1x1 的正方形（当然如果连 $(i, j)$ 本身都未被填充，那就不构成任何正方形）
考虑扩增的情况：如果三个位置本身都不只是代表一个被填充的点，而是作为边长为 2 的正方形的右下角的点，那么这就有一个边长为 2+1 = 3 的正方形；同理如果三个位置都代表了边长为 3 的正方形，那么就发现了一个边长为 3+1 = 4 的正方形。这样只要求取三个位置代表的正方形的边长 n，就可以得到当前最大的正方形的边长 n+1。
而我们使用右下角作为一个正方形的代表就是为了在从上到下和从左到右扫描过程中确保其余三个位置都是已被求解过的。
def solve(matrix: List[List[str]]) -> int:
n = len(matrix[0])
w = 0
# right-down corner
dp0 = [0] * (n+1)
dp1 = [0] * (n+1)
for row in matrix:
for i in range(1, n+1):
if row[i-1] == '1':
dp1[i] = min(dp1[i-1], dp0[i], dp0[i-1]) + 1
else:
dp1[i] = 0
w = max(w, max(dp1))
dp1, dp0 = dp0, dp1
return w * w
运行时间：551 ms (beats 98.7%)，内存占用：19.25 MB (beats 62.82%, ~100%)。
241. Different Ways to Add Parentheses
这个题从题干背景上看，非常类似于前面的 22. Generate Parentheses ，但是有所不同，特别是对于迭代版本来说。
首先从尝试从文本中分离出操作数和操作符45，因为都是二元操作符，那么显然操作数和操作符之间存在对应关系，从索引下标的角度说，第一部分的操作数的坐标也就是它的操作符的坐标。这样问题就转变成了一个我们熟悉的、形式化的单串上的问题。
计算所有括号可能的添加的产生的值，可以先把这个操作数串分成任意两部分，计算它们在第一个部分结尾对应的操作符运算下所产生的的值，而每一部分的值又可以进一步地缩小规模，直到称为单个操作数。这就是我们解的思路。
迭代版本
对于递归的版本，解的实现很简单，但是对于迭代版本就有些细节需要考虑：
首先，不同于一般地串上 DP 的算法，这里不能直接用嵌套扫描的矿建递推子问题，而是一层扫描一层长度的变革；
其次，存储中间结果的二维数组（考虑到存储得是列表，实际上是三维数组）应该使用“起始位置-长度”而不是“起始位置-结束位置”的结构，这个优化是从 1278. Palindrome Partitioning III 里用过的；
最后，有一些实用的简化代码的 Python 技巧，
- 使用
product代替合并两部分结果的嵌套循环； - 用两层的列表循环代替 for 循环；
- 直接保存二元操作符，而不是字符，然后条件判断
原始代码：
for j in range(i, i+l-1): # the last but one
for a in dp[i][j-i]:
for b in dp[j+1][(i+l-1)-(j+1)]:
if op[j] == '+':
dp[i][l-1].append(a+b)
elif op[j] == '-':
dp[i][l-1].append(a-b)
else:
dp[i][l-1].append(a*b)
优化后的代码：
dp[i][l-1] = [
op[j](a, b)
for j in range(i, i+l-1) # the last but one
for a, b in product(dp[i][j-i], dp[j+1][(i+l-1)-(j+1)])
]
完整版本：
from itertools import product
from typing import List
from string import digits
from operator import mul, sub, add
def solve(expr: str) -> List[int]:
ope = []
op = []
n = len(expr)
i = 0
while i < n:
if expr[i] == "+":
op.append(add)
elif expr[i] == "-":
op.append(sub)
elif expr[i] == "*":
op.append(mul)
elif i + 1 < n and expr[i + 1] in digits:
ope.append(int(expr[i : i + 2]))
i += 1
else:
ope.append(int(expr[i]))
i += 1
m = len(ope)
#start -> #len (0..)
dp = [[None for _ in range(m-i)] for i in range(m)]
for l in range(1, m+1):
for i in range(m-l+1):
if l == 1:
dp[i][0] = [ope[i]]
else:
dp[i][l-1] = [
op[j](a, b)
for j in range(i, i+l-1) # the last but one
for a, b in product(dp[i][j-i], dp[j+1][(i+l-1)-(j+1)])
]
return dp[0][m-1]
运行时间：36 ms (beats 87.09%)，内存占用： 17.54 MB (beats 5.02%) 。
递归版本
递归版本就非常简单，细节前面都已经彻底地讨论过了。
from functools import cache
from itertools import product
from typing import List
from string import digits
from operator import mul, sub, add
def solve(expr: str) -> List[int]:
ope = []
op = []
n = len(expr)
i = 0
while i < n:
if expr[i] == "+":
op.append(add)
elif expr[i] == "-":
op.append(sub)
elif expr[i] == "*":
op.append(mul)
elif i + 1 < n and expr[i + 1] in digits:
ope.append(int(expr[i : i + 2]))
i += 1
else:
ope.append(int(expr[i]))
i += 1
m = len(ope)
@cache
def dfs(i, j) -> List[int]:
if j - i == 0:
return [ope[i]]
return [
op[k](a, b)
for k in range(i, j)
for a, b in product(dfs(i, k), dfs(k + 1, j))
]
return list(dfs(0, m - 1))
运行时间：28 ms (beats 99.19%)，内存占用： 17.69 MB (beats 5.02%) 。
但是必须吐槽下这里即使不缓存计算结果，也不影响运行时间的指标
注解
