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;