1. 动态规划
动态规划(Dynamic Programming, DP)是一种通过将复杂问题分解为更小的子问题来求解的算法设计思想,一般用于求解具有最优子结构和重叠子问题性质的问题。动态规划的核心在于:(1)最优子结构--问题的最优解可以由其子问题的最优解构造而来;(2)重叠子问题--在递归求解时,同一子问题会被多次计算。(3)状态转移--通过已解决的子问题计算更大的问题。通过保存已经计算过的子问题的解(通常用数组),可以避免重复计算,从而提高效率。
动态规划一般包括以下几个步骤:
- 定义状态:用一个数组(或多个数组)表示问题在某个阶段的解。
- 确定状态转移方程:找到状态之间的递推关系。
- 初始化:设置基础状态的值(边界条件)。
- 按顺序计算:根据状态转移方程填充状态表。
- 返回结果:从状态表中得到问题的解。
2. 问题例子
例子1: 最长公共子序列
- 两个字符串中,不要求连续但要求相对顺序一致的子序列。
- 例如:对于字符串
ABCD
和AEBD
,最长公共子序列是ABD
,长度为 3。
1. 状态定义
- 定义 dp[i][j] 表示 和 的最长公共子序列的长度。
- 其中 表示字符串 的前 i 个字符。
2. 边界条件
- 当 i = 0 或 j = 0 时,空字符串与任意字符串的最长公共子序列长度为 0。因此:
3. 状态转移方程
若当前字符相等(即 ),则最长公共子序列可以通过将这两个相等字符加入到和 的最长公共子序列得到,转移公式为:
若当前字符不相等,则最长公共子序列的长度取决于以下两种情况的较大值:
- 只考虑 和 的最长公共子序列;
- 只考虑和 的最长公共子序列;
- 因此:
4. 结果计算
即为字符串 和 的最长公共子序列的长度,其中 m 和 n 分别是两个字符串的长度。
5. 代码
def longest_common_subsequence(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] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]
例子2: 最长公共子串
- 两个字符串中,要求连续且相同的子串。
- 例如:对于字符串
ABCD
和AEBD
,最长公共子串是B
,长度为 1。
1. 状态定义
令 表示字符串 和 的以 和 结尾的最长公共子串的长度。
2. 边界条件
- 当 i = 0 或 j = 0 时,空字符串无法形成公共子串,因此:
3. 状态转移方程
- 如果当前字符相等(即 ),则当前的最长公共子串长度是之前的最长公共子串长度加 1:
- 如果当前字符不相等,则当前没有公共子串:
4. 结果计算
- 在整个动态规划表 dp[i][j] 中找到最大值,即为最长公共子串的长度。
- 如果需要具体的子串,可以通过记录最大值的位置,回溯得到对应的子串。
5. 代码
def longest_common_substring(text1, text2):m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)]max_length = 0end_pos = 0 # 记录子串结束位置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] + 1if dp[i][j] > max_length:max_length = dp[i][j]end_pos = ielse:dp[i][j] = 0# 返回最长公共子串及其长度return text1[end_pos - max_length:end_pos], max_length
例子3: 最长回文子序列
给定一个字符串 S ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列
1. 状态定义
设 dp[i][j] 表示字符串 s 的下标区间 [i, j] 内的最长回文子序列长度:
- dp[i][j] 是子字符串 s[i:j+1] 的最长回文子序列长度。
2. 递推关系
如果两端字符相同(),则最长回文子序列的长度为:
当前回文子序列的两端字符 和 相同,子问题规模缩小为中间部分。
如果两端字符不同(),则最长回文子序列为:
选择舍弃或 其中一个,递归处理子问题。
3. 边界条件
单个字符(长度为 1)自然是回文子序列,长度为 1:
4. 最终结果
最终结果存储在 ,即整个字符串的最长回文子序列长度。
5. 代码
def longest_palindrome_subseq(s):n = len(s)dp = [[0] * n for _ in range(n)]for i in range(n - 1, -1, -1):dp[i][i] = 1for j in range(i + 1, n):if s[i] == s[j]:dp[i][j] = dp[i + 1][j - 1] + 2else:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])return dp[0][n - 1]
例子4: 最长回文子串
给定一个字符串 S,找到其中最长的回文子串(要求子串是连续的,且回文即正序和反序相同)。
1. 状态定义
令 表示字符串 是否为回文子串:
- ,表示 是回文子串;
- ,表示 不是回文子串。
2. 转移方程
- 如果 ,那么字符串 是否是回文只取决于内部子串 :
, 当且仅当
- 特殊情况:
子串长度为 1 时(即 i = j),所有单个字符都是回文:
子串长度为 2 时(即 j = i + 1),只要两个字符相等就是回文:
3. 初始化
动态规划的计算顺序是从子串长度短到长。需要:
- 初始化所有长度为 1 的子串为回文;
- 判断长度为 2 的子串;
- 按子串长度递增计算更长的子串。
4. 结果计算
在构造 dp 表的过程中,记录最长回文子串的起始位置和长度。
5. 代码
def longest_palindrome_substring(s):n = len(s)if n < 2:return smax_len = 1begin = 0dp = [[False] * n for _ in range(n)]for i in range(n):dp[i][i] = True# 先枚举子串长度for L in range(2, n + 1):for i in range(n):# 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得j = L + i - 1if j >= n:breakif s[i] != s[j]:dp[i][j] = False else:if j - i < 3:dp[i][j] = Trueelse:dp[i][j] = dp[i + 1][j - 1]if dp[i][j] and j - i + 1 > max_len:max_len = j - i + 1begin = ireturn s[begin:begin + max_len]
3. 参考材料
【1】区间 DP:最长回文子序列