codeforces 163A A. Substring and Subsequence(dp)
题目链接:codeforces 163A题目大意:给出两个字符串,求第一个字符串的子串和第二个字符串的子序列相等的个数。题目分析:定义状态dp[i][j]表示s的子串以i结尾,t的子序列以j结尾的相等的对数。转移方程很简单,就是当某一位上两个字符相等的时候,dp[i][j]=∑k<jdp[i−1][k]dp[i][j] = \sum_{k<j} dp[i-1][k] AC代码:#include