动态规划（最长公共子序列）

动态规划（Dynamic Programming）是一种常用的算法思想，它通过将原问题分解为若干个子问题的解来求解原问题。在进行子问题的求解时，动态规划会保存已经求解过的子问题的结果，以便后续使用。这样，可以避免重复计算，提高算法的效率。

最长公共子序列（Longest Common Subsequence，简称LCS）是一个经典的动态规划问题。给定两个字符串S和T，求它们的最长公共子序列的长度。子序列是指从原序列中删除若干个元素后得到的序列，而不要求删除的元素的位置相邻。

我们可以定义一个二维数组dp[i][j]，表示S的前i个字符和T的前j个字符的最长公共子序列的长度。则有以下状态转移方程：

- 当S[i]==T[j]时，dp[i][j] = dp[i-1][j-1] + 1；
- 当S[i]!=T[j]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

其中，当S[i]==T[j]时，表示S的第i个字符和T的第j个字符都在最长公共子序列中，那么这个最长公共子序列的长度就是S的前i-1个字符和T的前j-1个字符的最长公共子序列的长度再加上1。当S[i]!=T[j]时，表示S的第i个字符和T的第j个字符不可能同时在最长公共子序列中，那么最长公共子序列的长度就是S的前i-1个字符和T的前j个字符的最长公共子序列的长度，或者是S的前i个字符和T的前j-1个字符的最长公共子序列的长度中的较大值。

最终，最长公共子序列的长度就是dp[m][n]，其中m和n分别是S和T的长度。

代码实现如下：

def longest_common_subsequence(S, T):
    m, n = len(S), len(T)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if S[i-1] == T[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

时间复杂度为O(mn)，空间复杂度为O(mn)。