DP-最长公共子序列

动态规划（DP）常见的应用场景包括：最长、最优、最大、最小、计数等类型的问题。

解题思路是先写出递归式，再将其转换为 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;