DP

套路：最长 ， 最优，最大，最小，最长，计数

先写出递归式

1string sa = "abcd";
2string sb = "becd";
3
4int f(int a, int b)
5{
6	if (a == 0 || b == 0)return 0;
7	//最小规模为2个字符的比较
8	if (sa[a] == sb[b])
9	{
10		return  1+ f(a-1,b-1) ;//如果该2字符相等，那么计算下一条，最大程度加1
11	}
12	else
13	{
14		return max( f(a - 1, b), f(a, b - 1));// 如果不等 那么 a下一条或b下一条选择最大
15	}
16
17}

转换为DP的递推式，

1	int arr[10][10];
2	memset(arr, 0, 4 * 10 * 10);
3
4
5	for (int a = 1; a <= 4; a++)
6	for (int b = 1; b <= 4; b++)
7	{
8		if (sa[a] == sb[b])
9		{
10			arr[a][b] = 1 + arr[a - 1][b - 1];
11		}
12		else
13		{
14			arr[a][b] = max(arr[a + 1][b], arr[a][b + 1]);
15		}
16
17
18
19
20	}
21
22	cout << arr[4][4]<<endl;