1. 最长公共子序列（Longest Common Subsequence, LCS）
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
解题思路
使用动态规划，创建一个二维数组 dp，其中 dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列的长度。
代码实现
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
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]
2. 编辑距离（Edit Distance）
题目描述
给定两个单词 word1 和 word2，计算出将 word1 转换为 word2 所使用的最少操作次数。
解题思路
同样使用动态规划，dp[i][j] 表示 word1[0...i-1] 转换为 word2[0...j-1] 的最小编辑距离。
代码实现
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
return dp[m][n]
3. 不同的子序列（Distinct Subsequences）
题目描述
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
解题思路
依然使用动态规划，dp[i][j] 表示 S[0...i-1] 中包含 T[0...j-1] 的不同子序列的个数。
代码实现
def numDistinct(S, T):
m, n = len(S), len(T)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
if S[i - 1] == T[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
4. 最大子序和（Maximum Subarray）
题目描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少包含一个数字），并返回其最大和。
解题思路
使用动态规划，dp[i] 表示以 nums[i] 结尾的最大子序和。
代码实现
def maxSubArray(nums):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
max_sum = dp[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
5. 最小路径和（Minimum Path Sum）
题目描述
给定一个包含非负整数的 m x n 网格 grid，找出一条从左上角到右下角的路径，使得路径上的数字总和最小。
解题思路
使用动态规划，dp[i][j] 表示从左上角到 (i, j) 的最小路径和。
代码实现
def minPathSum(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 初始化第一行和第一列
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# 填充剩余的 dp 表
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
以上五个算法问题都是经典的高难度问题，它们在面试和算法竞赛中经常出现。通过动态规划的方式，我们可以有效地解决这些问题。希望这篇博客能帮助您更好地理解这些算法问题及其解决方案。如果您有任何疑问或建议，欢迎在评论区留言。