3动态规划进阶：序列DP深度解析

1. 序列DP概述

序列DP是动态规划中最常见和重要的类别之一，主要处理字符串、数组等序列上的问题。这类问题通常涉及子序列、子串、编辑距离等操作，是面试和竞赛中的高频考点。

2. 最长递增子序列 (LIS) 问题

2.1 最长递增子序列 (LeetCode 300)

问题描述：找到最长严格递增子序列的长度。

解法一：动态规划 O(n²)

def lengthOfLIS(nums):
"""
最长递增子序列 – 基础DP解法
时间复杂度：O(n²)
空间复杂度：O(n)
"""
if not nums:
return 0

n = len(nums)
# dp[i]表示以nums[i]结尾的最长递增子序列长度
dp = [1] * n

for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

#### Java实现
```java
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;

int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);

int maxLen = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}

return maxLen;
}
}

解法二：贪心 + 二分查找 O(n log n)

def lengthOfLIS_optimized(nums):
"""
最长递增子序列 – 贪心 + 二分优化
时间复杂度：O(n log n)
空间复杂度：O(n)
"""
if not nums:
return 0

tails = [] # tails[i]表示长度为i+1的递增子序列的最小末尾值

for num in nums:
# 二分查找插入位置
left, right = 0, len(tails)
while left < right:
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid

# 如果找到的位置等于tails长度，说明num比所有末尾值都大
if left == len(tails):
tails.append(num)
else:
tails[left] = num # 更新该长度的最小末尾值

return len(tails)

2.2 最长连续递增序列 (LeetCode 674)

问题描述：找到最长连续递增子数组的长度。

def findLengthOfLCIS(nums):
"""
最长连续递增序列
注意：连续 vs 不连续
"""
if not nums:
return 0

n = len(nums)
dp = [1] * n # dp[i]表示以nums[i]结尾的连续递增序列长度

for i in range(1, n):
if nums[i] > nums[i–1]:
dp[i] = dp[i–1] + 1

return max(dp)

# 空间优化版本
def findLengthOfLCIS_optimized(nums):
if not nums:
return 0

max_len = 1
curr_len = 1

for i in range(1, len(nums)):
if nums[i] > nums[i–1]:
curr_len += 1
max_len = max(max_len, curr_len)
else:
curr_len = 1

return max_len

Java实现

public class LongestContinuousIncreasingSubsequence {
public int findLengthOfLCIS(int[] nums) {
if (nums.length == 0) return 0;

int maxLen = 1;
int currLen = 1;

for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i–1]) {
currLen++;
maxLen = Math.max(maxLen, currLen);
} else {
currLen = 1;
}
}

return maxLen;
}
}

3. 最长公共子序列 (LCS) 问题

3.1 最长公共子序列 (LeetCode 1143)

问题描述：求两个字符串的最长公共子序列长度。

状态定义

dp[i][j]：text1前i个字符和text2前j个字符的LCS长度

状态转移方程

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])

Python实现

def longestCommonSubsequence(text1, text2):
"""
最长公共子序列
"""
m, n = len(text1), len(text2)

# dp[i][j]表示text1[0:i]和text2[0:j]的LCS长度
dp = [[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]:
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]

#### Java实现
```java
public class LongestCommonSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i–1) == text2.charAt(j–1)) {
dp[i][j] = dp[i–1][j–1] + 1;
} else {
dp[i][j] = Math.max(dp[i–1][j], dp[i][j–1]);
}
}
}

return dp[m][n];
}

// 空间优化版本
public int longestCommonSubsequenceOptimized(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[] dp = new int[n + 1];

for (int i = 1; i <= m; i++) {
int prev = 0; // 保存dp[i–1][j–1]
for (int j = 1; j <= n; j++) {
int temp = dp[j]; // 保存dp[i–1][j]
if (text1.charAt(i–1) == text2.charAt(j–1)) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j–1]);
}
prev = temp; // 更新prev为dp[i–1][j]
}
}

return dp[n];
}
}

3.2 编辑距离 (LeetCode 72)

问题描述：计算将word1转换为word2所需的最少操作数（插入、删除、替换）。

状态定义

dp[i][j]：word1前i个字符转换为word2前j个字符的最少操作数

状态转移方程

if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + 1, # 删除
dp[i][j-1] + 1, # 插入
dp[i-1][j-1] + 1 # 替换
)

Python实现

def minDistance(word1, word2):
"""
编辑距离
"""
m, n = len(word1), len(word2)

# dp[i][j]表示word1前i个字符转成word2前j个字符的最小编辑距离
dp = [[0] * (n + 1) for _ in range(m + 1)]

# 初始化：空字符串转换
for i in range(m + 1):
dp[i][0] = i # word1删除所有字符
for j in range(n + 1):
dp[0][j] = j # word1插入所有字符

for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i–1] == word2[j–1]:
dp[i][j] = dp[i–1][j–1]
else:
dp[i][j] = min(
dp[i–1][j] + 1, # 删除word1[i-1]
dp[i][j–1] + 1, # 在word1插入word2[j-1]
dp[i–1][j–1] + 1 # 替换word1[i-1]为word2[j-1]
)

return dp[m][n]

# 空间优化版本
def minDistance_optimized(word1, word2):
m, n = len(word1), len(word2)

# 使用两个数组滚动
prev = list(range(n + 1))

for i in range(1, m + 1):
curr = [i] * (n + 1) # 初始化第一列
for j in range(1, n + 1):
if word1[i–1] == word2[j–1]:
curr[j] = prev[j–1]
else:
curr[j] = min(
prev[j] + 1, # 删除
curr[j–1] + 1, # 插入
prev[j–1] + 1 # 替换
)
prev = curr

return prev[n]

Java实现

public class EditDistance {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];

// 初始化
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i–1) == word2.charAt(j–1)) {
dp[i][j] = dp[i–1][j–1];
} else {
dp[i][j] = Math.min(
Math.min(dp[i–1][j], dp[i][j–1]),
dp[i–1][j–1]
) + 1;
}
}
}

return dp[m][n];
}
}

4. 最大子数组和问题

4.1 最大子数组和 (LeetCode 53)

问题描述：找出具有最大和的连续子数组。

Kadane算法（动态规划变种）

def maxSubArray(nums):
"""
最大子数组和 – Kadane算法
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not nums:
return 0

curr_sum = nums[0]
max_sum = nums[0]

for i in range(1, len(nums)):
# 要么继续扩展当前子数组，要么重新开始
curr_sum = max(nums[i], curr_sum + nums[i])
max_sum = max(max_sum, curr_sum)

return max_sum

#### 标准DP解法
def maxSubArray_dp(nums):
"""
标准DP解法，便于理解
"""
n = len(nums)
dp = [0] * n # dp[i]表示以nums[i]结尾的最大子数组和
dp[0] = nums[0]
max_sum = nums[0]

for i in range(1, n):
dp[i] = max(nums[i], dp[i–1] + nums[i])
max_sum = max(max_sum, dp[i])

return max_sum

Java实现

public class MaximumSubarray {
public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;

int currSum = nums[0];
int maxSum = nums[0];

for (int i = 1; i < nums.length; i++) {
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}

return maxSum;
}
}

4.2 乘积最大子数组 (LeetCode 152)

问题描述：找出乘积最大的连续子数组（包含负数）。

思路：同时维护最大值和最小值

def maxProduct(nums):
"""
乘积最大子数组
关键：需要同时维护最大值和最小值（因为有负数）
"""
if not nums:
return 0

max_prod = nums[0]
min_prod = nums[0]
result = nums[0]

for i in range(1, len(nums)):
# 如果当前数是负数，交换最大值和最小值
if nums[i] < 0:
max_prod, min_prod = min_prod, max_prod

# 更新最大值和最小值
max_prod = max(nums[i], max_prod * nums[i])
min_prod = min(nums[i], min_prod * nums[i])

# 更新最终结果
result = max(result, max_prod)

return result

#### DP解法
def maxProduct_dp(nums):
n = len(nums)
if n == 0:
return 0

# dp_max[i]表示以nums[i]结尾的最大乘积
# dp_min[i]表示以nums[i]结尾的最小乘积
dp_max = [0] * n
dp_min = [0] * n
dp_max[0] = dp_min[0] = nums[0]
result = nums[0]

for i in range(1, n):
if nums[i] >= 0:
dp_max[i] = max(nums[i], dp_max[i–1] * nums[i])
dp_min[i] = min(nums[i], dp_min[i–1] * nums[i])
else:
dp_max[i] = max(nums[i], dp_min[i–1] * nums[i])
dp_min[i] = min(nums[i], dp_max[i–1] * nums[i])

result = max(result, dp_max[i])

return result

Java实现

public class MaximumProductSubarray {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;

int maxProd = nums[0];
int minProd = nums[0];
int result = nums[0];

for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = maxProd;
maxProd = minProd;
minProd = temp;
}

maxProd = Math.max(nums[i], maxProd * nums[i]);
minProd = Math.min(nums[i], minProd * nums[i]);

result = Math.max(result, maxProd);
}

return result;
}
}

5. 回文子序列/子串问题

5.1 回文子串 (LeetCode 647)

问题描述：计算字符串中回文子串的数量。

解法一：中心扩展法

def countSubstrings(s):
"""
回文子串数量 – 中心扩展法
时间复杂度：O(n²)
空间复杂度：O(1)
"""
n = len(s)
count = 0

def expand_around_center(left, right):
"""以(left, right)为中心扩展，统计回文子串"""
nonlocal count
while left >= 0 and right < n and s[left] == s[right]:
count += 1
left -= 1
right += 1

for i in range(n):
# 奇数长度回文，中心为单个字符
expand_around_center(i, i)
# 偶数长度回文，中心为两个字符
expand_around_center(i, i + 1)

return count

解法二：动态规划

def countSubstrings_dp(s):
"""
回文子串数量 – 动态规划
"""
n = len(s)
# dp[i][j]表示s[i:j+1]是否是回文
dp = [[False] * n for _ in range(n)]
count = 0

# 从下到上，从左到右遍历
for i in range(n–1, –1, –1):
for j in range(i, n):
# 单个字符是回文
if i == j:
dp[i][j] = True
count += 1
# 两个字符
elif j == i + 1:
dp[i][j] = (s[i] == s[j])
if dp[i][j]:
count += 1
# 三个及以上字符
else:
dp[i][j] = (s[i] == s[j] and dp[i+1][j–1])
if dp[i][j]:
count += 1

return count

Java实现

public class PalindromicSubstrings {
// 中心扩展法
public int countSubstrings(String s) {
int n = s.length();
int count = 0;

for (int i = 0; i < n; i++) {
// 奇数长度回文
count += expandAroundCenter(s, i, i);
// 偶数长度回文
count += expandAroundCenter(s, i, i + 1);
}

return count;
}

private int expandAroundCenter(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() &&
s.charAt(left) == s.charAt(right)) {
count++;
left—;
right++;
}
return count;
}

// 动态规划
public int countSubstringsDP(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;

for (int i = n – 1; i >= 0; i—) {
for (int j = i; j < n; j++) {
if (i == j) {
dp[i][j] = true;
count++;
} else if (j == i + 1) {
dp[i][j] = s.charAt(i) == s.charAt(j);
if (dp[i][j]) count++;
} else {
dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j–1];
if (dp[i][j]) count++;
}
}
}

return count;
}
}

5.2 最长回文子序列 (LeetCode 516)

问题描述：求最长回文子序列的长度（子序列不一定连续）。

状态定义

dp[i][j]：字符串s[i:j+1]的最长回文子序列长度

状态转移方程

if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Python实现

def longestPalindromeSubseq(s):
"""
最长回文子序列
注意：与最长回文子串的区别（子序列可以不连续）
"""
n = len(s)
# dp[i][j]表示s[i:j+1]的最长回文子序列长度
dp = [[0] * n for _ in range(n)]

# 对角线初始化：单个字符的回文长度为1
for i in range(n):
dp[i][i] = 1

# 从下到上，从左到右遍历
for i in range(n–1, –1, –1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j–1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j–1])

return dp[0][n–1]

# 空间优化版本
def longestPalindromeSubseq_optimized(s):
n = len(s)
dp = [0] * n

for i in range(n–1, –1, –1):
dp[i] = 1
prev = 0 # 保存dp[i+1][j-1]
for j in range(i+1, n):
temp = dp[j] # 保存dp[i+1][j]
if s[i] == s[j]:
dp[j] = prev + 2
else:
dp[j] = max(dp[j], dp[j–1])
prev = temp # 更新prev

return dp[n–1]

Java实现

public class LongestPalindromicSubsequence {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];

// 初始化对角线
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}

// 从下到上，从左到右
for (int i = n – 1; i >= 0; i—) {
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j–1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j–1]);
}
}
}

return dp[0][n–1];
}
}

6. 其他重要序列DP问题

6.1 解码方法 (LeetCode 91)

问题描述：数字字符串解码为字母（A=1, B=2, …, Z=26），求解码方法总数。

def numDecodings(s):
"""
解码方法
"""
if not s or s[0] == '0':
return 0

n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # 空字符串有1种解码方式
dp[1] = 1 # 第一个字符非0，有1种解码方式

for i in range(2, n + 1):
# 单字符解码
if s[i–1] != '0':
dp[i] += dp[i–1]

# 双字符解码
two_digit = int(s[i–2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i–2]

return dp[n]

# 空间优化版本
def numDecodings_optimized(s):
if not s or s[0] == '0':
return 0

n = len(s)
prev2, prev1 = 1, 1 # dp[i-2], dp[i-1]

for i in range(2, n + 1):
curr = 0

# 单字符解码
if s[i–1] != '0':
curr += prev1

# 双字符解码
two_digit = int(s[i–2:i])
if 10 <= two_digit <= 26:
curr += prev2

prev2, prev1 = prev1, curr

return prev1

Java实现

public class DecodeWays {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}

int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i <= n; i++) {
// 单字符解码
if (s.charAt(i–1) != '0') {
dp[i] += dp[i–1];
}

// 双字符解码
int twoDigit = Integer.parseInt(s.substring(i–2, i));
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i–2];
}
}

return dp[n];
}
}

6.2 等差数列划分 (LeetCode 413)

问题描述：计算数组中等差子数组的数量。

def numberOfArithmeticSlices(nums):
"""
等差数列划分
"""
n = len(nums)
if n < 3:
return 0

# dp[i]表示以nums[i]结尾的等差子数组个数
dp = [0] * n
total = 0

for i in range(2, n):
if nums[i] – nums[i–1] == nums[i–1] – nums[i–2]:
dp[i] = dp[i–1] + 1
total += dp[i]

return total

# 空间优化版本
def numberOfArithmeticSlices_optimized(nums):
n = len(nums)
if n < 3:
return 0

dp = 0 # 当前以nums[i]结尾的等差子数组个数
total = 0

for i in range(2, n):
if nums[i] – nums[i–1] == nums[i–1] – nums[i–2]:
dp += 1
total += dp
else:
dp = 0

return total

Java实现

public class ArithmeticSlices {
public int numberOfArithmeticSlices(int[] nums) {
int n = nums.length;
if (n < 3) return 0;

int dp = 0; // 以当前元素结尾的等差子数组个数
int total = 0;

for (int i = 2; i < n; i++) {
if (nums[i] – nums[i–1] == nums[i–1] – nums[i–2]) {
dp++;
total += dp;
} else {
dp = 0;
}
}

return total;
}
}

7. 序列DP解题模板总结

7.1 通用解题步骤

7.2 复杂度分析

7.3 常见模式识别

7.4 易错点提醒

7.5 进阶练习建议

8. 实战技巧

8.1 调试方法

8.2 优化思路

8.3 面试准备

掌握序列DP是动态规划进阶的关键，这些问题的解决思路和技巧将为后续更复杂的DP问题打下坚实基础。建议按类别系统练习，每类至少完成3-5道题目，确保真正掌握。