动态规划——1143. 最长公共子序列
时间:2022-05-11 10:33
动态规划——1143. 最长公共子序列
题目:
思路:
-
dp数组的定义:
二维dp数组,dp[i] [j]代表在text1[0, ... , i-1]和text2[0, ... , j-1]时,两个字符串的最长公共子序列的长度。 -
base_case:
dp[0] [j] = dp[i] [0] =0 -
状态转移方程:
代码:
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size() + 1;
int n = text2.size() + 1;
int a[m][n];
for(int i=0; i