最长公共子串 动态规划

最长公共子串 动态规划
题目
给定2个字符串，试求出这2个字符串的最长公共子串的长度。
输入格式
输入共2行，每行一个字符串。字符均为小写英文字母。
输出格式
仅一行，包含一个正整数，表示2个字符串的最长公共子串长度。
输入样例
ababc cbaab
输出样例
2
数据范围与提示:
对于30%的数据，保证字符串长度不超过10； 对于60%的数据，保证字符串长度不超过100； 对于90%的数据，保证字符串长度不超过1000； 对于100%的数据，保证字符串长度不超过5000；
动态规划三步骤
思路：将两个字符串组合成如上图的二维数组，首先定义一个dp二维数组并明确其定义，dp[i][j]的含义是第i，j位置的最长公共子串的长度。然后确定递推公式，我们思考元素之间的关系是什么，如图可以看出来如果连着匹配字符串，那么dp[i][j]=dp[i-1][j-1]+1,就是在斜对角线加1。我

最长公共子串 动态规划最先出现在Python成神之路。