一、最长递增子序列（Leetcode 300）
1.dp数组定义：
dp[i] 为以 nums[i] 结尾的最长递增子序列长度。
2.状态转移：
dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i]
2.dp数组初始化：
所有 dp[i] = 1，每个元素自身构成一个序列。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
# 初始化 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
dp = [1] * n # 每个元素自身至少是一个长度为1的递增子序列
# 遍历所有元素，尝试更新 dp[i]
for i in range(n):
for j in range(i):
# 如果前一个元素小于当前元素，说明可以递增
if nums[j] < nums[i]:
# 更新 dp[i]：取之前小于它的元素能形成的最长递增子序列 +1
dp[i] = max(dp[i], dp[j] + 1)
# 最终答案是 dp 数组中的最大值
return max(dp)
二、最长连续递增序列（Leetcode 674）
相比题一多了要求“连续”
1.dp数组定义：
dp[i] 为以 nums[i] 结尾的最长递增子序列长度。
2.状态转移：
dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[j] < nums[i]
2.dp数组初始化：
所有 dp[i] = 1，每个元素自身构成一个序列。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return 1
dp = [1] * n # 初始化：每个位置至少是1
max_len = 1 # 用于记录最大值
for i in range(1, n):
if nums[i] > nums[i - 1]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = 1
max_len = max(max_len, dp[i]) # 更新最大长度
return max_len
三、最长重复子数组 （Leetcode 718）
1.dp数组及下标定义
dp[i][j] 表示：以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。
2.状态转移方程：
若
nums1[i-1] == nums2[j-1]：
dp[i][j] = dp[i-1][j-1] + 1否则：
dp[i][j] = 0（连续子数组中断）
3.dp数组初始化：
根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1
所以dp[i][0] 和dp[0][j]初始化为0。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
n, m = len(nums1), len(nums2)
# 初始化 dp 数组，dp[i][j] 表示 nums1 前 i 个元素与 nums2 前 j 个元素
# 的最长公共子数组（结尾必须是 nums1[i-1] 与 nums2[j-1]）的长度
dp = [[0] * (m + 1) for _ in range(n + 1)]
max_len = 0 # 记录最长公共子数组的长度
# 遍历 nums1 和 nums2 所有元素
for i in range(1, n + 1):
for j in range(1, m + 1):
# 如果当前两个元素相等，更新 dp 值
if nums1[i - 1] == nums2[j - 1]:
# 在两个前缀都减 1 的基础上加 1
dp[i][j] = dp[i - 1][j - 1] + 1
# 更新最大长度
max_len = max(max_len, dp[i][j])
# 否则默认 dp[i][j] = 0（初始化时已经为 0）
return max_len
4.dp数组初始化注意事项：
dp = [[0] * (列数) for _ in range(行数)]
那么你的外层循环必须是 for i in range(行数 - 1)，
内层循环是 for j in range(列数 - 1)，并且数组元素访问要对应上。
四、最长公共子序列 （Leetcode 1143）
1.dp数组定义：
dp[i][j] 表示：text1 的前 i 个字符 和 text2 的前 j 个字符 的最长公共子序列长度
2.状态转移：
如果 text1[i - 1] == text2[j - 1]，说明当前字符可以匹配：
dp[i][j] = dp[i - 1][j - 1] + 1
否则假设在比较字符串 text1[0..i-1] 和 text2[0..j-1]：
当前字符不匹配：
text1[i - 1] != text2[j - 1]
这意味着：我们无法把这两个字符都纳入公共子序列中。
我们有两个选择：
跳过 text1[i - 1]，继续比较前 i-1 个字符与前 j 个字符
即：
dp[i - 1][j]
跳过 text2[j - 1]，继续比较前 i 个字符与前 j-1 个字符
即：
dp[i][j - 1]
我们选择其中 能构成更长公共子序列的路径，所以取最大值：
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
2.dp数组初始化：
dp[0][*] 和 dp[*][0] = 0，表示有一个空串时，LCS 为 0
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# 创建 dp 数组，额外多一行一列用于处理边界
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 遍历每个字符
for i in range(1, m + 1):
for j in range(1, n + 1):
# 如果当前字符相同，匹配成功，继承左上角 +1
if text1[i - 1] == text2[j - 1]:
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]