最长公共子序列
题目理解
返回给定两个字符串的最长公共子序列的长度。
思路
用动态规划的思路：
1.DP数组代表两个字符串的最长公共子序列的长度；
2.递推公式：DP[i][j]=DP[i-1][j-1]+1
3.初始化：DP[0][0]=DP[0][j]=DP[i][0]=0
4.遍历顺序：从前往后；
4.DP数组举例：
text1=ace
text2=abcde
DP[0][0]=1
DP[1][1]=1
DP[2][2]=2
DP[3][2]=2
DP[4][2]=3
问题1：发生堆缓冲区溢出
原因分析：数组索引越界，如果定义二维数组的大小是DP[text1.size()][text2.size()];那么我能索引到最远的地方是[text1.size()-1][text2.size()-1]
解决方法：修改数组大小：
vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
问题2
原因分析：我的遍历是从DP[1][1]开始的，没有考虑到text1[0]和text2[0]的情况；
解决方法：
if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
} elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
小结
自己开天辟地地想，没有思路，但是在明确这是当前的状态需要由前面的状态推导而来，即这是动态规划思路后，用动态规划的顺序往下写，竟然也写得差不离儿。有几个细节需要注意：(1)给定字符串的长度分别是i和j;(2)如果没有发生递增的条件，需要保留上一个大值。
不相交的线
问题描述
相当于返回两个数组中相同元素个数，但是不相交说明是按照顺序排列。与最大公共子序列不同的地方在于最大公共子序列中元素是相邻的。
解法在此不再赘述。