文章目录
-
- 原题题目
- 代码实现（首刷部分看解部分自解）
- 代码实现（二刷C++ 二刷自解）
- 代码实现（三刷自解 DAY 223 C++）
- 代码实现（四刷自解 DAY 280 C++）
- 代码实现（五刷自解 DAY 5 Golang）
原题题目
代码实现（首刷部分看解部分自解）
int longestCommonSubsequence(char * text1, char * text2){
int x = strlen(text1),y = strlen(text2),i,j;int dp[y+1][x+1];for(i=0;i<=x;i++)dp[0][i] = 0;for(i=0;i<=y;i++)dp[i][0] = 0;for(i=1;i<=y;i++){
for(j=1;j<=x;j++){
if(text1[j-1] == text2[i-1])dp[i][j] = dp[i-1][j-1] +1;elsedp[i][j] = fmax(dp[i-1][j],dp[i][j-1]);}}return dp[y][x];
}
代码实现（二刷C++ 二刷自解）
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {
int strl1 = text1.size(),strl2 = text2.size();vector<vector<int>> dp(strl1+1,vector<int>(strl2+1,0));for(int i=1;i<=strl1;i++){
for(int j=1;j<=strl2;j++){
if(text1[i-1] == text2[j-1])dp[i][j] = dp[i-1][j-1]+1;elsedp[i][j] = fmax(dp[i-1][j],dp[i][j-1]);}}return dp[strl1][strl2];}
};
代码实现（三刷自解 DAY 223 C++）
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),0));int size1 = text1.size(),size2 = text2.size();for(int i = 0;i < size1;++i){
for(int j = 0;j < size2;++j){
if(i) dp[i][j] = max(dp[i-1][j],dp[i][j]);if(j) dp[i][j] = max(dp[i][j-1],dp[i][j]);if(text1[i] == text2[j]){
dp[i][j] = 1;if(i && j) dp[i][j] = dp[i-1][j-1] + 1;}}}return dp[size1-1][size2-1];}
};
代码实现（四刷自解 DAY 280 C++）
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {
int size1 = text1.size(), size2 = text2.size();vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1, 0));for (int i = 1; i <= size1; ++i) {
for (int j = 1; j <= size2; ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if(text1[i - 1] == text2[j - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);}}return dp[size1][size2];}
};
代码实现（五刷自解 DAY 5 Golang）
func max(x, y int) int {
if x >= y {
return x} else {
return y}
}func longestCommonSubsequence(text1 string, text2 string) int {
dp := make([][]int, len(text1) + 1)for i, _ := range dp {
dp[i] = make([]int, len(text2) + 1)}for i := 1; i <= len(text1); i++ {
for j := 1; j <= len(text2); j++ {
if text1[i - 1] == text2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1} else {
dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]))}} }return dp[len(dp) - 1][len(dp[0]) - 1]
}