前言
动态规划是大厂的热门考点，其中最长公共子串与最长公共子序列这两道题出现得尤其频繁，这两道题其实有挺多变种，很适合考察侯选人对动态规划的掌握情况，今天我们就先来看看如何求解最长公共子串，图文并茂，清晰易懂！
最长公共子串
题目如下：
输入: x = ["", "a", "b", "c", "a", "d", "f"] y = ["", "a", "c", "b", "a", "d"],输出: 2解释: 最长公共子串为 ad，所以结果为 2这里需要简单解释下子串与子序列的区别，子串要求这串字符串在原字符串中是连续的，而子序列可以不连续，两者的区别如下：
小结一下
首先看下，如果这题如果用暴力求解的话，应该算出每个字符串的所有子字符串，然后再对所有子字符串进行比较，是个排列组合问题，时间复杂度很大，不可取！所以我们看下怎么用动态规划来解。
解动态规划需要至少明确以下三个概念
- base case
- 状态转移方程
- 自下而上
动态规划一言以蔽之就是利用 「base case 」和「状态转移方程」然后「自下而上」得求得最终问题的解。相对递归的自上而下求解造成的大量子问题的计算，自下而上意味着每个子问题不会被重复计算，很好地达到了「剪枝」的效果。这其中「状态转移方程」的求解无疑是重要的，如果求得了「状态转移」方程，问题其实就解决地差不多了。
回到最长公共子串本身来看，我们来看看它的「状态转移方程」和「base case」是啥。
1、状态转移方程
这题的状态转移方程该怎么定义呢，首先我们求的是两个字符串的公共子串，所以应该意识到这个 dp 方程是个二维数组 dp[i][j]，代表的 x 的前 i 个字符串与 y 的 前 j 个字符串的最长公共子串,
那么状态状态方程该怎么得出来呢，一般对于字符串类的动态规划来说，我们可以利用「状态转移表」法来帮助我们得出状态转移方程
观察出规律了吗，对于 dp[i][j] 来说，它的值有两种可能，取决于字符 x[i] 和 y[j] 这两个字符是否相等
如果两个字符相等，则 dp[i][j] = dp[i-1][j-1] + 1（注意图中的箭头）, 怎么理解，1 代表 x 的第 i 个字符与 y 的第 j 个字符相等，根据 dp[i][j] 的定义，那么它自然等于 x 的前 i-1 个字符串与 y 的 前 j-1 个字符串的最长公共子串 + 1，如下图示
如果 x 的第 i 个字符与 y 的第 j 个字符不相等，那么显然 dp[i][j] = 0，因为 dp[i][j] 定义为最长公共子串，所以只要有一个字符不相等，就说明不满足最长公共子串这个定义，自然 dp[i][j] 为 0 了。
根据以上条件可知状态转移方程为：
2、base case
显然图中黄色格子所示为 base case
即可用如下公式表示
这也比较好理解，dp[0][i] 或 dp[j][0] 即空字符串与任意字符串的最大公共子串显然为0。
3、求解
这里需要注意下标，因为我们的i、j是从1开始遍历，而我们的字符串字符下标是从0开始的，所以应该是i-1和j-1， 这里 i j代表的是字符串的长度，所以是从1开始 因为0的是初始值都为0
代码实现：
这里给出C++代码(C语言代码见上图)，实现了输出最长的公共子串
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
int main(){string s1,s2;cin>>s1>>s2;if(s1.size() > s2.size()) //以短的作为s1swap(s1,s2);int len1 = s1.size(), len2 = s2.size();int start = 0, mx = 0; //记录结果vector<vector<int> > dp(len1+1,vector<int>(len2+1,0));for(int i = 1;i<=len1;i++){for(int j = 1;j<=len2;j++){if(s1[i-1] == s2[j-1])dp[i][j] = dp[i-1][j-1] + 1;if(dp[i][j] > mx){mx = dp[i][j];start = i - mx;}}}cout<<s1.substr(start,mx);return 0;
}
