/*
* @lc app=leetcode.cn id=1143 lang=cpp
*
* [1143] 最長公共子序列
*
* https://leetcode-cn.com/problems/longest-common-subsequence/description/
*
* algorithms
* Medium (62.30%)
* Likes: 528
* Dislikes: 0
* Total Accepted: 113.1K
* Total Submissions: 181.5K
* Testcase Example: '"abcde"\n"ace"'
*
* 給定兩個字元串 text1 和 text2，傳回這兩個字元串的最長 公共子序列 的長度。如果不存在 公共子序列 ，傳回 0 。
*
* 一個字元串的 子序列
* 是指這樣一個新的字元串：它是由原字元串在不改變字元的相對順序的情況下删除某些字元（也可以不删除任何字元）後組成的新字元串。
*
*
* 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
*
*
* 兩個字元串的 公共子序列 是這兩個字元串所共同擁有的子序列。
*
*
*
* 示例 1：
*
*
* 輸入：text1 = "abcde", text2 = "ace"
* 輸出：3
* 解釋：最長公共子序列是 "ace" ，它的長度為 3 。
*
*
* 示例 2：
*
*
* 輸入：text1 = "abc", text2 = "abc"
* 輸出：3
* 解釋：最長公共子序列是 "abc" ，它的長度為 3 。
*
*
* 示例 3：
*
*
* 輸入：text1 = "abc", text2 = "def"
* 輸出：0
* 解釋：兩個字元串沒有公共子序列，傳回 0 。
*
*
*
*
* 提示：
*
*
* 1
* text1 和 text2 僅由小寫英文字元組成。
*
*
*/ 1.基本概念
首先需要科普一下，最長公共子序列（longest common sequence）和最長公共子串（longest common substring）不是一回事兒。什麼是子序列呢？即一個給定的序列的子序列，就是将給定序列中零個或多個元素去掉之後得到的結果。什麼是子串呢？給定串中任意個連續的字元組成的子序列稱為該串的子串。給一個圖再解釋一下：
如上圖，給定的字元序列： {a,b,c,d,e,f,g,h}，它的子序列示例： {a,c,e,f} 即元素b,d,g,h被去掉後，保持原有的元素序列所得到的結果就是子序列。同理，{a,h},{c,d,e}等都是它的子序列。
它的字串示例：{c,d,e,f} 即連續元素c,d,e,f組成的串是給定序列的字串。同理，{a,b,c,d},{g,h}等都是它的字串。
這個問題說明白後，最長公共子序列（以下都簡稱LCS）就很好了解了。
給定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}，s1和s2的相同子序列，且該子序列的長度最長，即是LCS。
s1和s2的其中一個最長公共子序列是 {3,4,6,7,8}
2.動态規劃
求解LCS問題，不能使用暴力搜尋方法。一個長度為n的序列擁有 2的n次方個子序列，它的時間複雜度是指數階，太恐怖了。解決LCS問題，需要借助動态規劃的思想。
動态規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動态規劃算法與分治法類似，其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重複計算了很多次。如果我們能夠儲存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重複計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，隻要它被計算過，就将其結果填入表中。這就是動态規劃法的基本思路。
3.特征分析
解決LCS問題，需要把原問題分解成若幹個子問題，是以需要刻畫LCS的特征。
設A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”為它們的最長公共子序列。不難證明有以下性質：
如果am=bn，則zk=am=bn，且“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一個最長公共子序列；
如果am!=bn，則若zk!=am，蘊涵“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一個最長公共子序列；
如果am!=bn，則若zk!=bn，蘊涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一個最長公共子序列。
有些同學，一看性質就容易暈菜，是以我給出一個圖來讓這些同學了解一下：
以我在第1小節舉的例子（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}），并結合上圖來說：
假如S1的最後一個元素 與 S2的最後一個元素相等，那麼S1和S2的LCS就等于 {S1減去最後一個元素} 與 {S2減去最後一個元素} 的 LCS 再加上 S1和S2相等的最後一個元素。
假如S1的最後一個元素 與 S2的最後一個元素不等（本例子就是屬于這種情況），那麼S1和S2的LCS就等于 ： {S1減去最後一個元素} 與 S2 的LCS， {S2減去最後一個元素} 與 S1 的LCS 中的最大的那個序列。
4.遞歸公式
第3節說了LCS的特征，我們可以發現，假設我需要求 a1 ... am 和 b1 .. b(n-1)的LCS 和 a1 ... a(m-1) 和 b1 .. bn的LCS，一定會遞歸地并且重複地把如a1... a(m-1) 與 b1 ... b(n-1) 的 LCS 計算幾次。是以我們需要一個資料結構來記錄中間結果，避免重複計算。
假設我們用c[i,j]表示Xi 和 Yj 的LCS的長度（直接儲存最長公共子序列的中間結果不現實，需要先借助LCS的長度）。其中X = {x1 ... xm}，Y ={y1...yn}，Xi = {x1 ... xi}，Yj={y1... yj}。可得遞歸公式如下：
5.計算LCS的長度
這裡我不打算貼出相應的代碼，隻想把這個過程說明白。還是以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}為例。我們借用《算法導論》中的推導圖：
圖中的空白格子需要填上相應的數字（這個數字就是c[i,j]的定義，記錄的LCS的長度值）。填的規則依據遞歸公式，簡單來說：如果橫豎（i,j）對應的兩個元素相等，該格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化該表：
然後，一行一行地從上往下填：
S1的元素3 與 S2的元素3 相等，是以 c[2,1] = c[1,0] + 1。繼續填充：
S1的元素3 與 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])，圖中c[1,2] 和 c[2,1] 背景色為淺黃色。
繼續填充：
中間幾行填寫規則不變，直接跳到最後一行：
至此，該表填完。根據性質，c[8,9] = S1 和 S2 的 LCS的長度，即為5。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size();
int n=text2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(text1[i-1]==text2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
}; 不需要使用額外數組的dp遞歸寫法
class Solution {
public:
int longestCommonSubsequence(string text1, string text2,int m,int n) {
if(m==0 || n==0){
return 0;
}
if(text1[m-1]==text2[n-1]){
return 1+longestCommonSubsequence(text1,text2,m-1,n-1);
}else{
return max(longestCommonSubsequence(text1,text2,m-1,n),longestCommonSubsequence(text1,text2,m,n-1));
}
}
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size(),n=text2.size();
return longestCommonSubsequence(text1,text2,m,n);
}
};