字符串上的简单动态规划

我就是我 2022-05-12 01:48 154阅读 0赞

因为数据结构快学串了，以前又做过一些字符串dp的题，今天突然就想把它们写在一起吧。

直接开始

问题1：给两个字符串，求最长公共子串

问题2：给两个字符串，求最长公共子序列

问题3：给一个字符串，求最长回文子串

问题4：给一个字符串，求最长回文子序列

问题5：给一个字符串，求将这个字符串变为回文串需要插入的最少字符个数。

问题6：最小编辑代价

问题7：判断交错组成

问题8：给一个字符串，求最长相同前后缀

问题9：给串a和b，判断b是否在a中出现，若出现输出第一次出现的位置。

# 问题1：给两个字符串，求最长公共子串 #

串和序列的区别之前提到过，串连续，序列可以不连续

如果连续那就比较好想了，定义DP(i，j）的含义是两个串分别以下标i和j结尾最长的公共子串长度。

如果a\[i\]=b\[j\]，那DP(i，j）=DP(i-1，j-1）+1，如果DP(i-1，j-1）=0，还是同样的操作，仅仅是之前不能构成而已，那i和j结尾的最长一定是1了。

如果a\[i\]!=b\[j\]，DP(i，j）=0，因为定义是以i和j结尾，一定不存在这样的相同子串。

初始化：先打第一行和第一列，相同为1，不同为0即可。

# 问题2：给两个字符串，求最长公共子序列 #

举例：

S1=“ABCBDAB.”

S2=“BABCBD.”

可以看出他们的最长公共子序列有ABCB,ABCD ,BCBD等，长度为4.

Dp(i,j)表示S的前i位与T的前j位的最长公共子串长度。

如果a\[i\]=b\[j\]，那DP(i，j）=DP(i-1，j-1）+1

否则，DP(i，j）=max（DP(i-1，j），DP(i，j-1））

仔细体会，手模拟几个就懂了。第一次想可能没那么容易

拓展：三个字符串：纯dp做

注：多个字符串要其他做法，以后数据结构学到串了或者树了再写。

# 问题3：给一个字符串，求最长回文子串 #

马拉车算法，我确实觉得也是动态规划思想，跳转看详细介绍吧

https://blog.csdn.net/hebtu666/article/details/79822584

# 问题4：给一个字符串，求最长回文子序列 #

对于任意字符串，如果头尾字符相同，那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾；如果首尾字符不同，则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。

因此动态规划的状态转移方程为：

设字符串为str，长度为n，p\[i\]\[j\]表示第i到第j个字符间的子序列的个数**（i<=j），**则：

状态初始条件：dp\[i\]\[i\]=1 （i=0：n-1）

状态转移方程：dp\[i\]\[j\]=dp\[i+1\]\[j-1\] + 2 if（str\[i\]==str\[j\]）

dp\[i\]\[j\]=max(dp\[i+1\]\[j\],dp\[i\]\[j-1\]) if （str\[i\]!=str\[j\]）

计算dp\[i\]\[j\]时需要计算dp\[i+1\]\[\*\]或dp\[\*\]\[j-1\]，因此i应该从大到小，即递减；j应该从小到大，即递增。注意必须满足i<=j的条件。

# 问题5：给一个字符串，求将这个字符串变为回文串需要插入的最少字符个数。 #

举例：

ab3bd

只需变为adb3bda即可，在前面插入d，在后面插入a;

思路：

设dp(i,j)为将Ai..Aj变为回文串的最小代价,如果a\[i\]=a\[j\]，那不用说了，肯定是dp(i,j)=dp(i+1,j-1),如果不相同，在前面或者后面插入一个字符，即dp(i,j)=min(dp(i,j-1),dp(i+1,j))+1

注意dp顺序：

for i:=n downto 1

for j:=i+1 to n

另一种思路：

将原串与原串的倒序做一次最长公共子序列，用原串长度减去最长公共子序列长度，即为需要插入字符的个数。逻辑很好想，不过多介绍

# 问题6：最小编辑代价 #

这个解释有点麻烦，思路分的比较多，是个值得好好思考一下的题。

\[题目\]

给定两个字符串str1 和str2，再给定三个整数ic、dc 和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。

(举例\]

str1="abc"，str2="adc"， ic=5, dc=3, rc=2。

从"abc"编辑成"adc"，把b'替换成'd是代价最小的，所以返回2。str1="abc"，str2="adc", ic=5， dc=3, rc=100。

从"abc"编辑成"adc"，先删除"b'， 然后插入d是代价最小的，所以返回8。str1="abc"，str2="abc", ic=5, dc=3, rc=2。

不用编辑了，本来就是一样的字符串，所以返回0。

思路：定义dp(i,j)为str1下标i之前编辑到str2下标j之前需要的最小代价。

Dp\[0\]\[0\]=0，空到空，不用改变。

矩阵dp第一列即dp\[..M-1\]\[0\]。dp\[i\]\[0\]表 示str1\[0..-1\]编辑成空串的最小代价，亳无疑问，是把str1\[..i1\]所有的字符删掉的代价，所以dp\[i\]\[0\]=dc\*i。

.矩阵dp第一行即dp\[0\]\[..N-1\]。 dp\[0\]\[j\]表示空串编辑成str2\[O.j-1\]的最小代价，亳无疑问，是在空串里插入str2\[0.j-1\]所有字符的代价，所以dp\[0\]\[\]=ic\*j。

其他位置按照从左到右，再从上到下来计算，dp\[i\]\[j\]的值只可能来自以下四种情况。

str1\[0.i-1\]可以先编辑成str1\[..i-2\]， 也就是删除字符str1\[i-1\]， 然后由str1\[0.i-2\]编辑成str2\[0.j-1\]， dp\[i-1\]\[i\]表 示str1\[0.i-2\]编辑成 str2\[0.j-1\]的 最小代价，那么dp\[i\]\[j\]可能等于dc+dp\[i-1\]\[j\]

str1\[0.i-1\]可以先编辑成str2\[0.j-2\], 然后将str2\[0.j-2\]插入字符str2\[j-1\]， 编辑成str2\[0.j-1\]，dp\[i\]\[j-1\]表 示str1\[..i-1\]编 辑成str2\[0.j-2\]的最小代价， 那么dp\[i\]\[j\]可能等于dp\[i\]\[j-1\]+ic。

如果str1\[i-1\]!=str2\[j-1\]。先把str1\[0.i-1\]中str1\[..i-2\]的 部分变成str2\[0.j-2\], 然后把字符str1\[i-1\]替换成str2\[-1\], 这样str1\[..i-1\]就编辑成str2\[0.j1\]了 。dp\[i-1\]\[j-1\]表示str1\[..i-2\]编辑成str2\[..i-2\]的最小代价，那么dp\[i\]\[j\]可 能等于dp\[i-1\]j-1\]+rc.

如果str1\[i-1\]==str2\[j-1\]. 先把str1\[0..i-1\]中 str1\[0..i-2\]的 部分变成str2\[0.j-2\], 因为此时字符str1\[i-1\]等 于str2\[j-1\]， 所以str1\[0.i-1\]已 经编辑成str2\[0.j-1\]了 。dp\[i-1\]\[j-1\]表示str1\[0i-2\]编辑 成str2\[..i-2\]的 最小代价，那么dp\[\]ij\]可能等于dp\[i-1\]\[j-1\]

# 问题7：判断交错组成 #

给定三个字符串strl str2和aim,如果aim包含且仅包含来自str1 和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现-一个函数，判断aim是否是str1和str2交错组成。

思路：做这个题一开始脑子没开窍，老想三维，表示str1的前i个和str2的前j个，组成aim的k个，但其实k只能是i+j，所以，dp\[i\]\[j\]为str1的前i个和str2的前j个能否组成aim（i+j）。

那就简单了，要么放i要么放j，都不行就是0，有一个可以就是1.

# 问题8：给一个字符串，求最长相同前后缀，前缀不包括最后一个字符，后缀不包括第一个字符。 #

注意看kmp的next数组思想。先看下面的再看这个

[https://blog.csdn.net/hebtu666/article/details/82492803][https_blog.csdn.net_hebtu666_article_details_82492803]

# 问题9：给串a和b，判断b是否在a中出现，若出现输出第一次出现的位置。 #

8和9看kmp详解：https://blog.csdn.net/hebtu666/article/details/79822446

[https_blog.csdn.net_hebtu666_article_details_82492803]: https://blog.csdn.net/hebtu666/article/details/82492803