文章目录
目录
文章目录
前言
一、动态规划思路简介
二、具体实现
1. 字符串问题
1.1 最长公共字符串
1.2.0 最长回文子串
1.2.1 最长回文子序列
2.编辑距离问题
2.1 判断子序列
2.2 编辑距离
总结
前言
上文提到动态规划的背包问题，本文继续介绍动态规划的另一种应用：子序列问题。子序列分为间断子序列与连续子序列，其中诸多问题例如最大递增子序列、最长回文串等等，都可以用动态规划的思路解决
一、动态规划思路简介
动态规划解题的关键有两步。
第一步是找出题目中量的递推关系式。动态规划的代码实现是依据递推关系展开的，找出递推关系是最关键，也是最先要处理的一件事情。
第二步是依据递推关系明确dp数组的下标含义，并进行正确的初始化。
接下来我们从一些具体问题看一下如何使用动态规划思路解决问题。
二、具体实现
1. 字符串问题
1.1 最长公共字符串
请编写一个 C 语言程序来查找两个字符串的最长公共子串（由字符串中连续的一段字符组成的字符串）
输入两个字符串str1和str2， 字符串长度范围均为[0, 200)。
输出两个字符串的最长公共子串，如果不存在公共子串，则输出“没有公共子串”；如果有多个最长公共子串，则输出str1中从左至右第一个最长公共子串。
示例输入
abbbcc
accd示例输出
cc解题思路：先寻找有没有递推关系式。观察发现，此类最长问题，一般有 “当前位”的最长公共字符串长度等于“前一位”的最长公共字符串长度加一。
由递推关系可知，遍历数组的方向应该从前往后遍历，并有dp[i]=dp[i-1]+1，此处i表示在字符串中的位置，dp[i]表示以第i位为结尾的公共字符串长度。
具体代码
#include<stdio.h>
#include<string.h>
int main(){
char a[300]={0},b[300]={0};
scanf("%s%s",a+1,b+1);
// dp[i][j]表示a的i位，b的j位相同的情况下 从前向后数公共字串的长度
int dp[300][300]={0};
//初始化为0的原因在于默认字符不相等，在遍历时检测是否相等，若相等则加一
int alen=strlen(a+1),blen=strlen(b+1);
int maxlen=0,maxLocation=1;
for(int i=1;i<=alen;i++){
for(int j=1;j<=blen;j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
if(maxlen<dp[i][j]){
maxlen=dp[i][j];
maxLocation=i-maxlen+1;//找起始位置
}
}
}
}
for(int i=0;i<maxlen;i++){
printf("%c",a[maxLocation+i]);
}
return 0;
}1.2.0 最长回文子串
5. 最长回文子串 - 力扣（LeetCode）
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"解题思路：观察回文串规律，发现回文串有如下特征：若回文串字符数为奇数，则以第i位为中心向左右检索，如果左右边缘的字符相等，则回文串字符数加二。若回文串字符为偶数，则以第i位与第 i+1 位为中心向左右检索。
设dp1[i]与dp2[i]，前者表示在第i位向前数有多少个回文字符，dp2同理。
代码样例：
char* longestPalindrome(char* s){
int dp1[1000]={0},dp2[1000]={0};
int len=strlen(s);
for(int i=0;i<len;i++){
//dp1[i]表示对i加上中心后一半的长度
while(i-dp1[i]>=0&&i+dp1[i]<len){
if(s[i-dp1[i]]!=s[i+dp1[i]])
break;
dp1[i]++;
}
if(s[i]==s[i+1]&&i+1<len){
while(i-dp2[i]>=0&&i+1+dp2[i]<len){
if(s[i-dp2[i]]!=s[i+1+dp2[i]])
break;
dp2[i]++;
}
}
}
int max=2*dp1[1]-1,maxlocation=0;
for(int i=0;i<len;i++){
dp1[i]=2*dp1[i]-1;
dp2[i]=2*dp2[i];
if(max<(dp1[i]>dp2[i]?dp1[i]:dp2[i])){
max=dp1[i]>dp2[i]?dp1[i]:dp2[i];
maxlocation=i+1-(max+1)/2;
}
}
char*a=(char*)malloc(1010);
strncpy(a,s+maxlocation,max);
a[max]=0;
return a;
}1.2.1 最长回文子序列
516. 最长回文子序列 - 力扣（LeetCode）
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。解题思路：回文数组规律一般可由中间向两边推知。故知，对于 i 到 j 的子序列而言，若s [ i ] = s [ j ] 。其最大回文子序列数必定是dp[ i +1] [ j -1 ]+2。若s [ i ]不等于s [ j ]，那么考虑加入左侧元素或右侧元素后能否使子序列数增加，即比较放入左侧元素与放入右侧元素后的最大子序列数。
if(s[left]==s[right]){
dp[left][right]=dp[left+1][right-1]+2;
}else{
int max=dp[left+1][right]>dp[left][right-1]?dp[left+1][right]:dp[left][right-1];
dp[left][right]=dp[left+1][right-1];
}在动态规划解题过程中，我们只考虑按遍历顺序下的当前步未知，前面已遍历过的dp应该已知，并不再考虑它们是怎么计算得出的。因此对遍历顺序有较强的要求。
对于dp[ i ][ j ]，i 表示左边界，j 表示右边界，dp[ i ][ j ]表示最大序列数。因为计算dp[ i ][ j ]需要
dp[ i+1][ j ] dp[ i+1 ][ j-1] dp[ i ][ j-1]，所以遍历顺序应该i递减，j递增，从而保持完备性。
示例代码：
int longestPalindromeSubseq(char* s) {
int dp[1010][1010]={0};
//表示从i到j的最长回文序列
int len=strlen(s);
for(int i=0;i<len;i++)
dp[i][i]=1;
for(int left=len-1;left>=0;left--){
for(int right=left+1;right<len;right++){
if(s[left]==s[right]){
dp[left][right]=dp[left+1][right-1]+2;
}else{
int max=dp[left+1][right]>dp[left][right-1]?dp[left+1][right]:dp[left][right-1];
dp[left][right]=max;
}
}
}
return dp[0][len-1];
}2.编辑距离问题
2.1 判断子序列
392. 判断子序列 - 力扣（LeetCode）
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例1
输入：s = "abc", t = "ahbgdc"
输出：true示例2
输入：s = "axc", t = "ahbgdc"
输出：false解题思路：f[i][j] 存储了从位置 i 开始，字符 j + 'a' 在字符串 t 中的下一个出现位置。首先初始化 f 数组并填充，之后遍历 s 中的每个字符，在 f 数组中找到对应字符的下一个出现位置并更新。如果在任何时刻无法找到字符，返回 false，否则返回 true。
具体代码：
bool isSubsequence(char* s, char* t) {
int n = strlen(s), m = strlen(t);
int f[m + 1][26];
memset(f, 0, sizeof(f));
for (int i = 0; i < 26; i++) {
f[m][i] = m;
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
if (t[i] == j + 'a')
f[i][j] = i;
else
f[i][j] = f[i + 1][j];
}
}
int add = 0;
for (int i = 0; i < n; i++) {
if (f[add][s[i] - 'a'] == m) {
return false;
}
add = f[add][s[i] - 'a'] + 1;
}
return true;
}2.2 编辑距离
72. 编辑距离 - 力扣（LeetCode）
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
-
插入一个字符
-
删除一个字符
-
替换一个字符
示例1
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例2
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')解题思路：
定义一个 dp 数组，dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 的最小编辑距离。然后初始化 dp 数组的第一行和第一列，分别代表从空字符串到其他字符串的编辑距离。
对每一对字符 (word1[i-1], word2[j-1])，如果相等，dp[i][j] = dp[i-1][j-1]，否则考虑三种操作（删除、插入、替换），选择最小值。
最终结果在 dp[n][m]，其中 n 和 m 分别是 word1 和 word2 的长度。
具体代码：
int minDistance(char* word1, char* word2) {
int n = strlen(word1), m = strlen(word2);
int dp[n+1][m+1];
// 初始化边界条件
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
// 填充 dp 数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int cost = (word1[i-1] == word2[j-1]) ? 0 : 1;
dp[i][j] = fmin(fmin(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + cost);
}
}
return dp[n][m];
}总结
动态规划在子序列问题中应用广泛，关键是找出递推关系并设计合适的 dp 数组。通过精妙的状态转移，可以高效解决如最长公共子串、回文子序列及编辑距离等问题。
