[dp]leetcode1143：最长公共子序列LCS (medium)_字符串公共子串长度 leetcode

题目：

题解：

• 动态规划的经典例题，可参考晴神的算法笔记
• 首先先使用暴力法思考吧，设t1和t2的长度分别为m和n，那么对两个字符串中的每个字符，分别只有选和不选两个决策，而得到两个子序列后，比较两个子序列是否相同又需要O(max(m,n))，这样总复杂度为O(2^m+n x max(m,n))，这样无法承受数据大的情况。
• 动态规划求最长公共子序列（Longest Common Subsequence，简称 LCS）
• 状态：dp[i][j]表示t1[1…i]和t2[1…j]的LCS长度（下标从1开始）
• 状态转移方程：
• 1）若t1[i]==t2[j]，则表示t1和t2的LCS增加一位了，即dp[i][j]=dp[i-1][j-1]+1。
• 2）若t1[i]!=t2[j]，则表示t1和t2的LCS无法延伸，那么我们将t1[i]和t2[j]分别加入dp[i-1][j-1]中，看谁的LCS长即可。

代码如下：

class Solution {
public:
    //题解：动态规划，dp[i][j]表示t1[1...i]和t2[1...j]的LCS长度（下标从1开始）
    //状态转移方程：若t1[i]==t2[j]，则表示t1和t2的LCS增加一位了，即dp[i][j]=dp[i-1][j-1]+1。
    //若t1[i]!=t2[j]，则表示t1和t2的LCS无法延伸，那么我们将t1[i]和t2[j]分别加入dp[i-1][j-1]中，看谁的LCS长即可
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();
        int dp[m+1][n+1];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j]=1+dp[i-1][j-1];
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22