Day 53|1143.最长公共子序列 | 1035.不相交的线 |53. 最大子序和 动态规划

**Day53|1143. 最长公共子序列 |1035. 不相交的线 |53. 最大子序和**

在本篇文章中，我们将讨论三个动态规划问题：最长公共子序列（LCS）、不相交的线和最大子序和。这些问题都涉及到寻找一个最优解，或者说是找到一个满足某些条件的最长或最短的序列。

###1. 最长公共子序列 (1143)

**问题描述：**

给定两个字符串 `X` 和 `Y`，求出它们的最长公共子序列（LCS）。最长公共子序列是指这两个字符串中共同出现的最大子序列。

**动态规划解决方案：**

我们可以使用一个二维数组 `dp` 来存储从第0 个字符到第 i 个字符的 `X` 和从第0 个字符到第 j 个字符的 `Y` 的最长公共子序列。其中，`dp[i][j]` 表示从第0 个字符到第 i 个字符的 `X` 和从第0 个字符到第 j 个字符的 `Y` 的最长公共子序列。

def longestCommonSubsequence(X, Y):
 m = len(X)
 n = len(Y)

 # 初始化 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 X[i -1] == Y[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]

###2. 不相交的线 (1035)

**问题描述：**

给定一个矩阵 `grid`，其中每个元素都是一个整数。求出从左上角到右下角的最长不相交线段的长度。

**动态规划解决方案：**

我们可以使用一个二维数组 `dp` 来存储从左上角到当前位置的最长不相交线段的长度。其中，`dp[i][j]` 表示从左上角到 `(i, j)` 的最长不相交线段的长度。

def longestLine(grid):
 m = len(grid)
 n = len(grid[0])

 # 初始化 dp 数组 dp = [[0] *3 for _ in range(m)]

 # 填充 dp 数组 for i in range(m):
 for j in range(n):
 if i ==0 and j ==0:
 dp[i][0] = grid[i][j]
 elif i ==0:
 dp[i][1] = max(dp[i][0], dp[i][1]) + grid[i][j]
 elif j ==0:
 dp[i][2] = max(dp[i-1][2], dp[i][2]) + grid[i][j]
 else:
 dp[i][0] = max(max(dp[i-1][0], dp[i][0]), max(dp[i-1][1], dp[i-1][2])) + grid[i][j]

 # 返回最长不相交线段的长度 return max(max(row) for row in dp)

###3. 最大子序和 (53)

**问题描述：**

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

**动态规划解决方案：**

我们可以使用一个一维数组 `dp` 来存储从第0 个元素到当前元素的最大子序列和。其中，`dp[i]` 表示从第0 个元素到第 i 个元素的最大子序列和。

def maxSubArray(nums):
 m = len(nums)

 # 初始化 dp 数组 dp = [0] * m # 填充 dp 数组 for i in range(m):
 if i ==0:
 dp[i] = nums[i]
 else:
 dp[i] = max(dp[i-1], nums[i]) + nums[i]

 # 返回最大子序列和 return max(dp)

以上就是这三个动态规划问题的解决方案。这些问题都涉及到寻找一个最优解，或者说是找到一个满足某些条件的最长或最短的序列。