[HOT 100]今日一练------最长公共子序列

题目链接https://leetcode.cn/problems/longest-common-subsequence/submissions/723235700/?envTypestudy-plan-v2envIdtop-100-liked思路LCS模板题多维动态规划dp[i][j]中i表示text1j表示text2初始化注意有0行0列动态转移方程为字符相等时dp[i][j] dp[i-1][j-1] 1字符不相等时dp[i][j] Math.max(dp[i-1][j], dp[i][j-1])以text1 abcde, text2 ace为例则填表如下代码class Solution { //动态规划 dp[i][j]: i表示text1 j表示text2 //转移方程 //字符相等dp[i][j] dp[i-1][j-1] 1 //字符不等dp[i][j] max(dp[i-1][j], dp[i][j-1]) public int longestCommonSubsequence(String text1, String text2) { int l1 text1.length(); int l2 text2.length(); int[][] dp new int[l11][l21]; for(int i 1; i l1; i) for(int j 1; j l2; j) { if(text1.charAt(i-1) text2.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[l1][l2]; } }