DP-最长公共子序列

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

先写出递归式

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;