动态规划一日一题-10-10-最长公共子序列

最长公共子序列

---

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

---

这题也是经典的双串的线性dp问题，按照模板来进行分析即可。

状态表示：dp[i] [j] 表示串a的1-i与串b的1-j之间的最长common子序列。所以最终答案的返回值应该是dp[n] [m] ;

状态属性：max

base case：dp[i] [0] = 0 ; dp[0] [j] = 0 ;

状态转移：按照典型的字符相等判断

​ 如果两者是相等的，dp[i] [j] = dp[i-1] [j-1] + 1 ;

​ 如果不等 ， dp[i] [ j] = max(dp[i-1] [j] , dp[ i] [j-1]) ;

#include 

using namespace std ;

const int N = 1010 ; 

int f[N][N] ; 

char a[N] , b[N] ; 

int main()
{
    int n , m ; 
    
    cin >> n >> m ; 
    
    scanf("%s%s" , a + 1 , b + 1) ; 
    
    for(int i = 1 ;  i <= n ; ++i)
        a[i][0] = 0  ; 
    for(int j = 1 ; j <= m ; ++j)
        a[0][j] = 0 ; 
    
    for(int i = 1 ;  i <= n ; ++i )
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            if(a[i] == b[j])
            {
                f[i][j] = f[i-1][j-1] + 1 ; 
            }
            else
            {
                f[i][j] = max(f[i-1][j] , f[i][j-1]) ;
            }
        }
    }
    cout << f[n][m] << endl ; 
    return  0 ; 
}

经典的模板题，按照模板走即可，没有什么说的。