(LeetCode 热题 100) 1143. 最长公共子序列（动态规划dp）

题目：1143. 最长公共子序列

思路：经典动态规划dp题型，时间复杂度为0(n^2)。

C++版本：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size(),m=text2.size();
        //状态f[i][j]表示：text1[0,i]和text2[0,j]之间的最长公共子序列
        vector<vector<int>> f(n+1,vector<int>(m+1,0));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
            	//相等的话
                if(text1[i]==text2[j]){
                    f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+1);
                }
                //不相等的话
                f[i+1][j+1]=max(f[i+1][j+1],f[i+1][j]);
                f[i+1][j+1]=max(f[i+1][j+1],f[i][j+1]);
            }
        }
        return f[n][m];
    }
};

JAVA 版本：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n=text1.length(),m=text2.length();
        //状态f[i][j]表示：text1[0,i]和text2[0,j]之间的最长公共子序列
        int[][] f =new int[n+1][m+1];
        /*
        for(var x:f){
            Arrays.fill(x,0);
        }
        */
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
            	//相等的话
                if(text1.charAt(i)==text2.charAt(j)){
                    f[i+1][j+1]=Math.max(f[i+1][j+1],f[i][j]+1);
                }
                //不相等的话
                f[i+1][j+1]=Math.max(f[i+1][j+1],f[i+1][j]);
                f[i+1][j+1]=Math.max(f[i+1][j+1],f[i][j+1]);
            }
        }
        return f[n][m];
    }
}