# 方法一

$dp\left[i\right]\left[j\right]=dp\left[i-1\right]\left[j-1\right]dp\left[i\right]\left[j\right] = dp\left[i-1\right]\left[j-1\right]$                             $\left(s\left[i-1\right]==s\left[j-1\right]\right)\left(s\left[i-1\right]==s\left[j-1\right]\right)$
$dp\left[i\right]\left[j\right]=max\left(dp\left[i-1\right]\left[j\right],dp\left[i\right]\left[j-1\right]dp\left[i\right]\left[j\right] = max\left(dp\left[i-1\right]\left[j\right],dp\left[i\right]\left[j-1\right]$    $\left(s\left[i-1\right]!=s\left[j-1\right]\right)\left(s\left[i-1\right]!=s\left[j-1\right]\right)$

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


# 方法二

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* s1和s2最长公共子序列的长度
* @param s1 string字符串
* @param s2 string字符串
* @return int整型
*/
int LCS(string s1, string s2) {
// write code here
int a[1001],b[1001];
int n = s1.size(), m = s2.size();
//为了满足空间复杂度为min(n,m)
int len = min(n,m);
//交换s1,s2，保证s2是较短的，为了正确地做循环
if (len==n)
{
string ss = s1;
s1 = s2;
s2 = ss;
}
for (int i=0;i<=len;i++)
a[i]=0;

for (int i=1;i<=s1.size();i++)
{
for (int j=1;j<=s2.size();j++)
{
if (s1[i-1]==s2[j-1])
b[j] = a[j-1] + 1;
else
b[j] = max(b[j-1],a[j]);
}
//这里用b覆盖a
for (int j=0;j<=s2.size();j++)
{
a[j] = b[j];
b[j] = 0;
}
}
return a[s2.size()];
}
};