动态规划应用例子两枚::最长公共
welcome!
最长重复子数组 [力扣718]
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
解析:
//定义二维数组dp[i][j].
//其中行数和列数分别是两个数组的长度+1;(请自行思考:为什么是+1?)
//dp[i][j]表征:以A中A[i-1]为结尾的子串,和B中以B[j-1]结尾的子串,,,若他俩相
//等,就用他俩作为两串子数列A[0~i-1],B[0~j-1]的公共最长子数组,,,,,的长度.
//eg.,若dp[4][5]=3,就说明A[1]A[2]A[3]组成的Asub,与,B[2],B[3],B[4]组成的
//Bsub,这两个子串完全相同,长度是3.这个3还表示最长,即,A[0]A[1]A[2]A[3]
//与B[1]B[2],B[3],B[4]肯定不相同,(相同就是4了).
//注意,可以不从0开始,但是一定要i-1和j-1结尾
//这样,当i,j分别是A.size(),B.size()时,dp[i][j]就记录了两串数列以及其子列串所有的公共串的长度信息,只要取得其最大值即答案.
//那么状态转移方程如何取得?
//dp[i+1][j+1]与dp[i][j]具有怎样的联系呢??
//回顾一下定义:
//dp[i][j]表征:以A中A[i-1]为结尾的子串,和B中以B[j-1]结尾的子串,,,若他俩相
//等,就用他俩作为两串子数列A[0~i-1],B[0~j-1]的公共最长子数组,,,,,的长度.
//那么 dp[i+1][j+1]表征:A以A[i]为结尾的子串,和B以B[j]结尾的子串,若二者
//相等,就用这两串数列作为两串子数列A[0~i],B[0~j]的公共数组.得到的公共
//最长子数组长度.
//也就是说,dp[i+1][j+1]与dp[i][j],差了A[i]与B[j]两个数字的比较
//若A[i]==B[j],那么根据定义, dp[i+1][j+1]=dp[i][j] + 1;
//若A[i]!=B[j],dp[i+1][j+1]=0;(这里,子串Asub和子串Bsub的最后一个数字
//都不想等,他俩就一定不会相等,那么他倆就不是公共子数列,如果强行让他俩
//作为公共序列,,,,那么得到的最长的公共长度当然是0,,,这么做很无聊,呵呵
//呵)
//有了之前的分析,代码就很简单了:
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size()+1,vector<int>(B.size()+1,0));
int maxlen = 0;
for(int i=0;i<A.size();++i)
{
for(int j=0;j<B.size();j++)
{
if(A[i]==B[j])
dp[i+1][j+1]=dp[i][j] + 1;
maxlen = max(maxlen, dp[i+1][j+1]);
}
}
return maxlen;
}
};
最长公共子序列 力扣1143
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
解析:
//首先注意到,这道题和上一道题有区别,这道题的子序列可以是断开的,
//只要相对顺序不变就行,上一道题的子数组必须是连续的.
//定义二维数组dp[i][j].
//其中行数和列数分别是两个数组的长度+1;(经过了上一道题为什么是+1各
//位应该是想清楚了吧~)
//dp[i][j]表征:以A[0~i-1],B[0~j-1]的公共最长子序列,,,,,相当于是子问题
//的长度.
//eg.A="abcdef",B="ace";
//A[0]='a',A[1]='b',A[2]='c',A[3]='d',A[4]='e',A[5]='f',
//B[0]='a',B[1]='c',B[2]='e'
//若dp[5][3]=3,就说明A[0],A[2],A[4]组成的Asub=ace,与,B[0],B[1],B[2]组成的Bsub=ace,这两个子串完全相同,且长度是3.这个3还表示最长,
//即,Asub和Bsub不可再增加字母,(否则就超过3了).
//注意,Asub和Bsu可以不用i-1和j-1结尾
//这样,当i,j分别是A.size(),B.size()时,dp[i][j]就记录了两串序列以及其子序列串所有的公共串的长度信息,只要取得其最大值即答案.
//那么状态转移方程如何取得?
//dp[i+1][j+1]与dp[i][j]具有怎样的联系呢??
//回顾一下定义:
//dp[i][j]表征:以A中A[i-1]为结尾的子序列,和B中以B[j-1]结尾的子序列,,,若他
//俩相等,就用他俩作为两串子子串A[0~i-1],B[0~j-1]的公共最长子序列,,,,,
//的长度.
//那么 dp[i+1][j+1]表征:A以A[i]为结尾的子序列,和B以B[j]结尾的子序列,若
//二者相等,就用这两串序列作为两串子序列A[0~i],B[0~j]的公共数组.得到的
//公共最长子序列长度.
//若A[i]==B[j],那么根据定义, dp[i+1][j+1]=dp[i][j] + 1;
//若A[i]!=B[j], 则说明这两个Asub和Bsub不是最长公共子序列.那么只需要求
//这个问题的两个子问题,取max即可.
//dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1));
int maxlen = 0;
for(int i = 0; i <text1.size(); i++){
for(int j = 0; j < text2.size(); j++){
if(text1[i] == text2[j]) dp[i+1][j+1] = dp[i][j] + 1;
else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
maxlen = max(maxlen, dp[i+1][j+1]);
}
}
return maxlen;
}
};
SUMMARY:
两道题,数字的子串需要相邻,字符的子序列可以分开只需要相对位置不变即可.
处理的方式大同小异.
数字题状态转移方程:
若A[i-1]==B[j-1] dp[i+1][j+1]=dp[i][j] + 1;
若A[i-1]!=B[j-1] dp[i+1][j+1]=0;
字符串题状态转移方程:
若text1[i] == text2[j] dp[i+1][j+1] = dp[i][j] + 1;
否则 dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
状态转移方程的相同点,是当两个串对应的值一样时候,都是去掉对应值之后的子串结果+1;
不同点是,当对应值不同时,数字题的下一个值为0;因为数字题的dp设定,Asub和Bsub必须以其作为结尾,做不成结尾就是0;而字符题相当于是大问题的子问题.
造成这种不同的根本原因在于,两道题的题干不同.数字题需要连续,字符题不需要连续.
作为数字题, dp[i+1][j+1]的状态只能由 dp[i][j]的状态转移而来.因为两个数组要同时加上相同的数字,公共子数组的长度才会+1.
而字符题目不需要.字符题目dp[i+1][j+1] 严格意义说是由
dp[i][j+1], dp[i+1][j]以及dp[i][j]三个状态转移而来的.
另外,本文对边界条件未加讨论.请根据dp[i][j]设定的具体意义正确赋值即可
(其实这两道题边界都是0)
over~