动态规划

1、最长公共子串问题

给定两个字符串str1和str2，返回两个字符串的最长公共子串。

1.1、经典方法：时间复杂度O(M*N)，额外空间复杂度O(M*N)。

生成大小为M*N的动态规划表dp[M][N]。dp[i][j]代表：在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下，公共子串最长能有多长。

如str1="abcde"，str2="bebcd"，计算dp矩阵如下：