1143. Longest Common Subsequence
从右往左递归，方便1:1翻译成从左往右的递推
[[0] _ (m+1) for _ in range((n+1))] 和 [[0] _ (m+1)] * (n+1) 的区别
好问题 👍 这两个看起来很像，但差别非常大。我们逐个分析：
1. 写法一：列表推导式
python
f = [[0] * (m+1) for _ in range(n+1)]- 每次循环都会新建一个 独立的列表。
- 所以总共有
n+1个不同的子列表。 - 修改某一行不会影响到其他行。
✅ 这是我们真正想要的二维数组（矩阵）。
例子：
python
m, n = 2, 2
f = [[0] * (m+1) for _ in range(n+1)]
f[0][0] = 1
print(f)输出：
text
[[1, 0, 0],
[0, 0, 0],
[0, 0, 0]]2. 写法二：列表乘法
python
f = [[0] * (m+1)] * (n+1)- 外层其实是把 同一个子列表的引用复制了 n+1 次。
- 所以所有行都指向同一个对象。
- 改动一行，其他行也会同时变。
❌ 这通常是 bug。
例子：
python
m, n = 2, 2
f = [[0] * (m+1)] * (n+1)
f[0][0] = 1
print(f)输出：
text
[[1, 0, 0],
[1, 0, 0],
[1, 0, 0]]可以看到，本来只改 f[0][0]，结果三行的第一列都变了。
✅ 总结
[[0] * (m+1) for _ in range(n+1)]→ 正确二维矩阵，行之间独立。[[0] * (m+1)] * (n+1)→ 每行其实是同一个列表的别名，修改会联动，容易出 bug。
python
#
# @lc app=leetcode.cn id=1143 lang=python3
#
# [1143] 最长公共子序列
#
# @lc code=start
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n = len(text1)
m = len(text2)
# @cache
# def dfs(i, j):
# if i < 0 or j < 0:
# return 0
# if text1[i] == text2[j]:
# return dfs(i-1, j-1) + 1
# return max(dfs(i-1, j), dfs(i, j-1))
# return dfs(n-1, m-1)
f = [[0] * (m+1) for _ in range((2))]
for i, x in enumerate(text1):
for j, y in enumerate(text2):
if x == y:
f[(i+1)%2][j+1] = f[i%2][j] + 1
else:
f[(i+1)%2][j+1] = max(f[i%2][j+1], f[(i+1)%2][j])
return f[n%2][m]
# @lc code=end