1143. 最长公共子序列(leetcode)

https://leetcode.cn/problems/longest-common-subsequence/description/
经典题,老题回顾

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // f[i][j]表示所有在第一个序列前i个数中选择,在第二个序列前j个数中选择得到的最长子序列,即最长公共子序列
        // 那么答案就是f[nums1.length][nums2.length]
        // 以nums1[i],nums2[j]是否选择来划分,那么就有四种情况,划分成四个子集
        // nums1[i],nums2[j]都不选
        // f[i][j]=f[i-1][j-1] // 这里可以忽略,因为后续的f[i-1][j]或者f[i][j-1]都是f[i-1][j-1]的超集
        // nums1[i],nums2[j]都选(这里都选就必须nums1[i]==nums2[j],因为是公共的)
        // f[i][j]=f[i-1][j-1]+1
        // nums1[i]选,nums2[j]不选 或者 nums1[i]不选.nums2[j]选
        // 这两种情况不好直接判断,只能使用f[i-1][j],f[i][j-1]来替代求答案
        // 因为f[i-1][j]是表示在前i-1中选择,前j中进行选择,不一定选择第j个,集合并不等价,而是父子集关系
        // 但是由于是题意求最大长度,那么父集合的最大长度是>=子集合最大长度的 , f[i][j-1]同理
        // 因此可以直接使用,而不用管递推是否合法
        // 因此f[i][j]=max(f[i-1][j-1]+1,f[i-1][j],f[i][j-1])
        // 初值全0即可,都合法
        
        int[][] f=new int[text1.length()+1][text2.length()+1];
        char[] t1=text1.toCharArray();
        char[] t2=text2.toCharArray();

        for(int i=1;i<=t1.length;i++)
        {
            for(int j=1;j<=t2.length;j++)
            {
                f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
                if(t1[i-1]==t2[j-1])f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
            }
        }
        return f[t1.length][t2.length];
    }
}