4.最长公共子序列

• 2.19

  • 将两个字符串想象成横坐标和纵坐标为 intdp 二维数组
  • 取如果两个字符相同，则下一个字符位置为左上+1，否则就是左或上
  • 返回最后的目标数组内的数，里面就是存的最长长度

• 2.5

  • 相等就加一（找左上角）。

  • 不等就继承（找左边和上边的最大值）。 这就是 LCS 问题的全部精髓。

  • • dp[i][j] 表示 text1 的 前 i 个字符 和 text2 的 前 j 个字符，它们的最长公共子序列是多少。

🧩 状态转移方程

分两种情况：

1️⃣ 如果两个字符相同：

即 text1[i-1] == text2[j-1] 那么： dp[i][j] = dp[i-1][j-1] + 1 因为这个字符可以“加入”前面形成的公共子序列中。

---

2️⃣ 如果两个字符不同：

那么我们可以选择：

• 去掉 text1 的最后一个字符，看看前面的最长公共子序列；
• 或去掉 text2 的最后一个字符。 取两者较大的： dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
            int m = text1.length(),n = text2.length();
            int[][] dp = new int[m+1][n+1];
            for(int i =1;i<m+1;i++){
                for(int j=1;j<n+1;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[m][n];
    }
}

5️⃣ i=5 (text1=e)

• j=1：不同 → 1
• j=2：不同 → 2
• j=3：相同（e=e）→ dp[5][3] = dp[4][2] + 1 = 3

i\j	""	a	c	e
""	0	0	0	0
a	0	1	1	1
b	0	1	1	1
c	0	1	2	2
d	0	1	2	2
e	0	1	2	3
相同(左上+1)
不同(max(上和左)