心路历程：

这道题还是按照之前公共子数组的角度去思考的话会超时，即考虑最后一个元素一定是公共子序列的最后一个元素。需要换一种建模思路，从而简化整个递推过程。

状态：以i, j为结尾的区间的最长公共子序列，text1[i]和text2[j]的大小关系
动作：是否选i-1，是否选j-1
返回值：最长公共子序列的长度

解法一：动态规划 + 不一定包含末尾元素的建模

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dp(i, j):  # 以text1[i], text2[j]为结尾的公共子序列的最长长度；
            if i == 0: return int(text1[0] in text2[:j+1])
            if j == 0: return int(text2[0] in text1[:i+1])
            if text1[i] == text2[j]:
                return dp(i-1, j-1) + 1
            else:
                return max(dp(i-1, j), dp(i, j-1))
  
        res = 0
        for i in range(len(text1)):
            for j in range(len(text2)):
                res = max(res, dp(i,j))
        return res

解法二 （超时）：动态规划 + 一定包含末尾元素的建模

class Solution:

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dp(i, j):  # 以text1[i], text2[j]为结尾的公共子序列的最长长度；
            if text1[i] != text2[j]: return 0
            if i == 0 or j == 0: return 1
            
            res = []
            for i1 in range(i-1, -1, -1):
                for j1 in range(j-1, -1, -1):
                    if text1[i1] == text2[j1]:
                        res.append(dp(i1, j1) + 1)
            if res != []: return max(res)
            else: return 1
        
        res = 0
        for i in range(len(text1)):
            for j in range(len(text2)):
                res = max(res, dp(i,j))
        return res