最长公共子序列(一)

class Solution {
public:
//给一个dp[i][j]  i当成s1当前长度，j为s2当前长度。
    int LCS(string s1, string s2) {
        vector<vector<int>>dp(s1.size()+1,vector<int>(s2.size()+1,0));
        int n1=s1.size(),n2=s2.size();
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
                if(s1[i-1]!=s2[j-1])
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            else dp[i][j]=dp[i-1][j-1]+1;
        }
        return dp[n1][n2];
    }
}; 

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# s1和s2最长公共子序列的长度
# @param s1 string字符串 
# @param s2 string字符串 
# @return int整型
#
class Solution:
    def LCS(self , s1: str, s2: str) -> int:
        # write code here
        dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]

        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

        return dp[-1][-1]

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * s1和s2最长公共子序列的长度
 * @param s1 string字符串 
 * @param s2 string字符串 
 * @return int整型
*/
func LCS( s1 string ,  s2 string ) int {
    m,n:=len(s1),len(s2)
    mat:=make([][]int,m+1)
    for i,_:=range mat{
        mat[i]=make([]int,n+1)
    }
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if s1[i]==s2[j]{
                mat[i+1][j+1]=mat[i][j]+1
            }else{
                mat[i+1][j+1]=max(mat[i][j+1],mat[i+1][j])
            }
        }
    }
    return mat[m][n]
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    public int LCS (String s1, String s2) {
        // write code here
        int maxLen=Math.max(s1.length(),s2.length())+1;
        int[][] f=new int[maxLen][maxLen];
        char[] chars1=new char[maxLen];
        char[] chars2=new char[maxLen];
        for(int i=0;i<maxLen;i++){
            if(i<s1.length()){
                chars1[i+1]=s1.charAt(i);
            }
            if(i<s2.length()){
                chars2[i+1]=s2.charAt(i);
            }
        }
        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
                if(chars1[i]==chars2[j]){
                    f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
                }
            }
        }
        return f[s1.length()][s2.length()];

    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串
     * @param s2 string字符串
     * @return int整型
     */
    public int LCS (String s1, String s2) {
        // write code here
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        for (int i = 1; i < s1.length() + 1; i ++) {
            for (int j = 1; j < s2.length() + 1; j ++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[s1.length()][s2.length()];
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        int m=s1.length();
        int n=s2.length();
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(s1[i-1]==s2[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];
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * s1和s2最长公共子序列的长度
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @return int整型
     */
    int LCS(string s1, string s2) {
        // write code here
        int m = s1.size();
        int n = s2.size();
        int dp[m+1][n+1];
        memset(dp, 0, (m+1)*(n+1)*sizeof(int));
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                if (s1[i-1] == s2[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];
    }
};