目录
- 前置知识
- LCS
- 举一反三
- LPS
前置知识
【算法】动态规划专题③ ——二维DP python
子序列定义为：
不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
LCS
最长公共子序列 https://www.lanqiao.cn/problems/1189/learning/?page=1&first_category_id=1&problem_id=1189
题目描述
给定一个长度为N数组a和一个长度为M的数组b。请
你求出它们的最长公共子序列长度为多少。
输入描述
输入第一行包含两个整数N,M,分别表示数组a和b的长度。
第二行包含N个整数a1,a2,…,an。
第三行包含M个整数b1,b2,…,bm
输出描述
输出一行整数表示答案。
1≤N,M≤1e3,1≤ai,bi≤1e9
思路：
定义dp[i][j]表示序列A的前i个元素和序列B的前j个元素之间的最长公共子序列的长度。
当 A[i-1] = B[j-1]，在这种情况下，dp[i][j] = dp[i-1][j-1] + 1
当 A[i-1] != B[j-1]，我们需要决定去掉 A[i]或者B[i]来寻找更大值
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
这里，dp[i-1][j]表示不包括A的第i个元素的最大LCS长度，而dp[i][j-1]表示不包括B的第j个元素的最大LCS长度
代码如下：
n, m = map(int, input().split())
a =list(map(int, input().split()))
b =list(map(int, input().split()))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):for j in range(1, m + 1):if a[i - 1] == b[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])print(dp[n][m])
通过路径回溯可以重建出具体的LCS
举一反三
两个字符串的删除操作 https://leetcode.cn/problems/delete-operation-for-two-strings/description/
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = “sea”, word2 = “eat”
输出: 2
解释: 第一步将 “sea” 变为 “ea” ，第二步将 "eat "变为 “ea”
示例 2:
输入：word1 = “leetcode”, word2 = “etco”
输出：4
提示：
1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母
思路：
计算 两个字符串的长度 和 最长公共子序列的长度之差即可
题解code：
class Solution:def minDistance(self, word1: str, word2: str) -> int:n, m = len(word1), len(word2)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, m + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return n + m - dp[n][m] * 2
LPS
最长回文子序列 https://leetcode.cn/problems/longest-palindromic-subsequence/description/
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成
思路：
LPS转化为LCS
将s和逆序的s做最长公共子序列即可得到最长回文子序列
code：
class Solution:def longestPalindromeSubseq(self, s: str) -> int:ss = s[::-1]n = len(s)dp = [[0] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, n + 1):if s[i - 1] == ss[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[n][n]
当然，在此介绍的不是最直接的做法
正规做法属于区间DP，后续会更新
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢
