dp学习:LIS与LCS

LIS: Longest Increasing Subsequence 最长上升子序列
LCS: Longest Common Subsequence 最长公共子序列

LIS是指对于给定序列，取出其中i个数(不能改变相对顺序)，这i个数严格单调递增，求最大的i
LCS是指给定两个序列，两个序列各取出i个元素(不能改变相对顺序)，这i个元素组成的两个新序列完全相同，求最大的i

最长上升子序列的两种解法(已有数组vector<int> v为序列记录，int n = v.size())：
解法一：O(n^2)

int main(){vector<int> dp(n, 1);for(int i = 0; i < n; i++){for(int j = 0; j < i; j++){if(v[i] > v[j]) v[i] = max(v[i], v[j]+1);}}int maxn = dp[0];for(int i : dp){maxn = max(maxn, i);}// 最终maxn即为所求
}

解法二：贪心+二分 O(n log n)

int main(){vector<int> low;for(int i = 0; i < n; i++){auto it = lower_bound(low.begin(), low.end(), v[i]);if(it == low.end()){low.push_back(v[i]);} else {*it = v[i];}}// 最终low.size()即为所求
}

解法二中，low数组第i位记录的是长度为i+1的上升子序列的最小的末尾值，可知当长度n的上升子序列的末尾值越小，可能存在的长度为n+1的上升子序列的数目会越多。
故解法二过程为：遍历序列，查找当前值在low数组中的位置，如果返回low.end()说明当前值比low中所有值都大，故插入到末尾；否则将对应位置更新为当前值。
最终遍历结束后我们就可以得到最长的序列长度。

最大公共子序列的解法：可知暴力的复杂度会随着元素数量n与m的增长而快速增长，为O(n*2^m)，故应当使用动态规划解决。

已知序列A长度为m，B长度为n

思考：如果A[m-1] == B[n-1],那么这个元素一定在LCS的序列中，如果A[m-1] != B[n-1], 那么LCS序列一定在A[m-1]与B[n-2]的LCS或A[m-2]与B[n-1]的LCS中。

故我们构建二维数组dp[i][j]来记录A[0到i-1]与B[0到j-1]的LCS，状态转移方程如下:

if(i == 0 || j == 0){  // 空序列没有LCSdp[i][j] = 0;
} else if(A[i-1] == B[j-1]){  // 当前字符相等，LCS为1+两方各减一个字符的LCSdp[i][j] = dp[i-1][j-1] + 1;
} else {  // 当前字符不相等，LCS一定从下述两种情况中来dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

完整代码如下：

int LCS(string &A, string &B) {int m = A.length(), n = B.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));  // 构建DP表// 依据转移方程填充DP表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (A[i-1] == B[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];
}int main() {string A = "ABCBDAB";string B = "BDCABA";cout << "LCS长度: " << LCS(A, B) << endl;  // 输出4return 0;
}