代码随想录算法训练营第三十八天 | 动态规划 Part11

638 字

3 分钟

代码随想录算法训练营第三十八天 | 动态规划 Part11

2025-07-24

算法

动态规划、子序列问题

/

LeetCode

/

Python

1143. 最长公共子序列#

LeetCode 1143. Longest Common Subsequence

思路：

定义 dp[i][j] 为 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度；
若 text1[i-1] == text2[j-1]，可以接在公共子序列后面；
否则，不等时，从左边或上边选一个最大值；
最终返回 dp[m][n]。

1
class Solution:
2
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
3
        m, n = len(text1), len(text2)
4
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 初始化 dp 表，全为 0
5
        for i in range(1, m + 1):
6
            for j in range(1, n + 1):
7
                if text1[i - 1] == text2[j - 1]:
8
                    # 当前字符相等，接在前一个公共子序列后
9
                    dp[i][j] = dp[i - 1][j - 1] + 1
10
                else:
11
                    # 不等时，取上方或左方较大者
12
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
13
        return dp[m][n]

1035. 不相交的线#

LeetCode 1035. Uncrossed Lines

思路：

本质是最长公共子序列问题；
两条线之间不能交叉，即要求相对顺序一致；
状态定义与转移方程与上题完全一致。

1
class Solution:
2
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
3
        m, n = len(nums1), len(nums2)
4
        dp = [[0] * (n + 1) for _ in range(m + 1)]
5
        for i in range(1, m + 1):
6
            for j in range(1, n + 1):
7
                if nums1[i - 1] == nums2[j - 1]:
8
                    # 连线的前提是两个数字相等
9
                    dp[i][j] = dp[i - 1][j - 1] + 1
10
                else:
11
                    # 不等时，不能连线，选左或上
12
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
13
        return dp[m][n]

53. 最大子序和#

LeetCode 53. Maximum Subarray

思路：

dp[i] 表示以 i 结尾的最大连续子数组和；
转移方程：
- dp[i] = max(dp[i - 1] + nums[i], nums[i])
- 即“选”或“重开”；
最终返回 max(dp) 即为所求。

1
class Solution:
2
    def maxSubArray(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        dp = [float('-inf')] * n  # 初始化为负无穷，防止全负数错误
5
        dp[0] = nums[0]
6
        for i in range(1, n):
7
            # 要么延续前一个子数组，要么重新开始
8
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
9
        return max(dp)  # 所有状态中最大值即为答案

392. 判断子序列#

LeetCode 392. Is Subsequence

思路（动态规划解法）：

定义 dp[i][j] 为 s[0..i-1] 和 t[0..j-1] 的最长公共子序列长度；
若 dp[m][n] == m，说明 s 是 t 的子序列；
其实也可以双指针写法更优（但此处为 DP 解法）。

1
class Solution:
2
    def isSubsequence(self, s: str, t: str) -> bool:
3
        m, n = len(s), len(t)
4
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp[i][j]: s前i和t前j的LCS长度
5
        for i in range(1, m + 1):
6
            for j in range(1, n + 1):
7
                if s[i - 1] == t[j - 1]:
8
                    dp[i][j] = dp[i - 1][j - 1] + 1
9
                else:
10
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
11
        # 如果整个 s 是 t 的子序列，则 dp[m][n] == m
12
        if dp[m][n] >= m:
13
            return True
14
        return False