代码随想录算法训练营 day53 | 1143.最长公共子序列、1035.不相交的线、53. 最大子序和 动态规划

**代码随想录算法训练营 Day53**

### **1143. 最长公共子序列**

#### **问题描述**

给定两个字符串 `text1` 和 `text2`, 返回它们的最长公共子序列（LCS）的长度。

#### **示例1:**

输入:`text1 = "abcde", text2 = "ace"` 输出:`3`

#### **示例2:**

输入:`text1 = "abc", text2 = "def"` 输出:`0`

#### **解决方案**

我们可以使用动态规划来解决这个问题。首先，我们定义一个二维数组 `dp`，其中 `dp[i][j]` 表示 `text1[0..i-1]` 和 `text2[0..j-1]` 的最长公共子序列的长度。

def longestCommonSubsequence(text1: str, text2: str) -> int:
 m, n = len(text1), len(text2)
 # 初始化 dp 数组 dp = [[0] * (n +1) for _ in range(m +1)]
 # 填充 dp 数组 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]

#### **注释**

* 我们首先初始化 `dp` 数组，大小为 `(m +1) x (n +1)`。
* 然后，我们填充 `dp` 数组。对于每个位置 `(i, j)`，我们检查 `text1[i -1]` 和 `text2[j -1]` 是否相等。如果相等，我们将 `dp[i -1][j -1] +1` 赋值给 `dp[i][j]`。否则，我们取 `dp[i -1][j]` 和 `dp[i][j -1]` 的最大值赋值给 `dp[i][j]`。
* 最后，我们返回 `dp[m][n]` 作为最长公共子序列的长度。

### **1035. 不相交的线**

#### **问题描述**

给定一个数组 `points`，其中每个元素是两个整数，表示一条水平或垂直线。请找出不相交的线的数量。

#### **示例1:**

输入:`points = [[1,1],[1,2],[3,4]]` 输出:`3`

#### **示例2:**

输入:`points = [[1,1],[2,2],[4,4],[8,5]]` 输出:`2`

#### **解决方案**

我们可以使用动态规划来解决这个问题。首先，我们定义一个二维数组 `dp`，其中 `dp[i][j]` 表示第 `i` 条线和第 `j` 条线是否相交。

def maxEqualRowsAfterFlips(points: list[list[int]]) -> int:
 m = len(points)
 # 初始化 dp 数组 dp = [[0] * (m +1) for _ in range(m +1)]
 # 填充 dp 数组 for i in range(1, m +1):
 for j in range(i, m +1):
 if points[i -1][0] == points[j -1][0]:
 dp[i][j] = dp[i -1][j]
 elif points[i -1][0] != points[j -1][0]:
 dp[i][j] = dp[i -1][j -1]
 # 返回不相交的线的数量 return m - dp[m][m]

#### **注释**

* 我们首先初始化 `dp` 数组，大小为 `(m +1) x (m +1)`。
* 然后，我们填充 `dp` 数组。对于每个位置 `(i, j)`，我们检查第 `i` 条线和第 `j` 条线是否有相同的 x 坐标。如果相同，我们将 `dp[i -1][j]` 赋值给 `dp[i][j]`。否则，我们取 `dp[i -1][j -1]` 的值赋值给 `dp[i][j]`。
* 最后，我们返回 `m - dp[m][m]` 作为不相交的线的数量。

### **53. 最大子序和**

#### **问题描述**

给定一个整数数组 `nums`，请找出最大子序列和。

#### **示例1:**

输入:`nums = [-2,1,-3,4,-1,2,1,-5,4]` 输出:`6`

#### **示例2:**

输入:`nums = [1]` 输出:`1`

#### **解决方案**

我们可以使用动态规划来解决这个问题。首先，我们定义一个一维数组 `dp`，其中 `dp[i]` 表示最大子序列和。

def maxSubarraySum(nums: list[int]) -> int:
 m = len(nums)
 # 初始化 dp 数组 dp = [0] * (m +1)
 # 填充 dp 数组 for i in range(1, m +1):
 if nums[i -1] > dp[i -1]:
 dp[i] = nums[i -1]
 else:
 dp[i] = dp[i -1] + nums[i -1]
 # 返回最大子序列和 return max(dp)

#### **注释**

* 我们首先初始化 `dp` 数组，大小为 `(m +1)`。
* 然后，我们填充 `dp` 数组。对于每个位置 `i`，我们检查当前数字是否大于前一个最大子序列和。如果大于，我们将当前数字赋值给 `dp[i]`。否则，我们取前一个最大子序列和加上当前数字赋值给 `dp[i]`。
* 最后，我们返回 `max(dp)` 作为最大子序列和。

以上就是本文的全部内容，希望对您有所帮助！