题意理解
给定序列 SSS 和 TTT，求有多少对子序列 (s′,t′)(s', t')(s′,t′)，使得 s′s's′ 是 SSS 的子序列，t′t't′ 是 TTT 的子序列，且 s′s's′ 和 t′t't′ 内容完全相同。
注意：不同下标组成的相同内容子序列视为不同。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
使用动态规划。
设 dp[i][j]dp[i][j]dp[i][j] 表示：SSS 的前 iii 个元素和 TTT 的前 jjj 个元素中，内容相同的子序列对数量。
状态转移：
考虑是否选择 S[i]S[i]S[i] 和 T[j]T[j]T[j]：
* 若 S[i−1]neqT[j−1]S[i-1] neq T[j-1]S[i−1]neqT[j−1]：无法同时选两者作为结尾
dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]
（容斥原理：不选 S[i]S[i]S[i] 的方案 + 不选 T[j]T[j]T[j] 的方案 - 重复计算的部分）
* 若 S[i−1]=T[j−1]S[i-1] = T[j-1]S[i−1]=T[j−1]：可以同时选两者作为新的结尾
dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]
（相当于上面的式子 + dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]，正好抵消）
边界条件：
* dp[i][0]=1dp[i][0] = 1dp[i][0]=1，dp[0][j]=1dp[0][j] = 1dp[0][j]=1：空序列与空序列配对，方案数为 1
答案： dp[n][m]dp[n][m]dp[n][m]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
