1韭脊、題目
image.png
2童谒、分析
求公共最長(zhǎng)子序列問(wèn)題，有個(gè)套路：
2.1 涉及兩個(gè)字符串/數(shù)組時(shí)（比如最長(zhǎng)公共子序列）沪羔，dp 數(shù)組的含義如下：
在子數(shù)組 arr1[0..i] 和子數(shù)組 arr2[0..j] 中饥伊，我們要求的子序列（最長(zhǎng)公共子序列）長(zhǎng)度為 dp[i][j]。
2.2 只涉及一個(gè)字符串/數(shù)組時(shí)（比如本文要講的最長(zhǎng)回文子序列），dp 數(shù)組的含義如下：
在子數(shù)組 array[i..j] 中琅豆，我們要求的子序列（最長(zhǎng)回文子序列）的長(zhǎng)度為 dp[i][j]愉豺。
引用自：https://labuladong.github.io/zgnb/3/15/20/
這道題目，只要明確了dp數(shù)組的含義茫因，很快就做出來(lái)了
3粒氧、代碼
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++){
dp[i][0] = 0;
}
for(int i = 0; i <= n; i++){
dp[0][i] = 0;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; 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][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
