【1143.最长公共子序列】【C++ 】 (labuladong#500)

Edwenc · Ed · labuladong · web-flow · commit 0ad9a50f645f · 2020-11-17T17:35:19.000+08:00
* add 1143 C++ version

* add comment

Co-authored-by: Ed &lt;hh@email.com&gt;
Co-authored-by: labuladong &lt;labuladong@foxmail.com&gt;
diff --git a/动态规划系列/最长公共子序列.md b/动态规划系列/最长公共子序列.md
@@ -1,4 +1,4 @@
-# 最长公共子序列
+﻿# 最长公共子序列
 
 
 <p align='center'>
@@ -149,6 +149,40 @@ else:
 
 ======其他语言代码======
 
+
+[Edwenc](https://github.com/Edwenc) 提供 C++ 代码：
+
+```C++
+class Solution {
+public:
+    int longestCommonSubsequence(string text1, string text2) {
+        //  先计算两条字符串的长度
+        int m = text1.size();
+        int n = text2.size();
+
+        //  构建dp矩阵  默认初始值0
+	//  这里会多扩建一边和一列  
+ 	//  因为dp[i][j]的含义是：对于 s1[1..i] 和 s2[1..j]，它们的LCS长度是 dp[i][j]。
+	//  所以当i或者j为零时  LCS的长度默认为0
+        vector< vector<int> > dp ( m+1 , vector<int> ( n+1 , 0 ) );
+
+        //  状态转移
+	//  i、j都从1开始遍历  因为下面的操作中都会-1  相当于从0开始  
+        for ( int i=1 ; i<m+1 ; i++ ){
+            for ( int j=1 ; j<n+1 ; j++ ){
+                //  如果text1和text2相同
+                //  就在它们的前一位基础上加一
+                //  如果不同  只能在之前的两者中去最大
+                dp[i][j] = (text1[i-1] == text2[j-1]) ? dp[i-1][j-1] + 1 : max( dp[i-1][j] , dp[i][j-1] );
+            }
+        }
+
+        //  返回最终右下角的值
+        return dp[m][n];
+    }
+};
+```
+
 [Shawn](https://github.com/Shawn-Hx) 提供 Java 代码：
 
 ```java
@@ -173,3 +207,4 @@ public int longestCommonSubsequence(String text1, String text2) {
 }
 ```
 
+
