套路:最长 , 最优,最大,最小,最长,计数
先写出递归式
string sa = "abcd";
string sb = "becd";
int f(int a, int b)
{
if (a == 0 || b == 0)return 0;
//最小规模为2个字符的比较
if (sa[a] == sb[b])
{
return 1+ f(a-1,b-1) ;//如果该2字符相等,那么计算下一条,最大程度加1
}
else
{
return max( f(a - 1, b), f(a, b - 1));// 如果不等 那么 a下一条或b下一条选择最大
}
}
转换为DP的递推式,
int arr[10][10];
memset(arr, 0, 4 * 10 * 10);
for (int a = 1; a <= 4; a++)
for (int b = 1; b <= 4; b++)
{
if (sa[a] == sb[b])
{
arr[a][b] = 1 + arr[a - 1][b - 1];
}
else
{
arr[a][b] = max(arr[a + 1][b], arr[a][b + 1]);
}
}
cout << arr[4][4]<<endl;