算法|算法：最大公共子串( 二 )
这是因为如果str1[m]==str2[n]，dp[m+1] [n+1]=dp[m] [n]+1，而对于str1中m为0，str2中n为0时，如果用dp[0] [0]来保存，则没有dp[-1] [-1]的元素（数组元素下标最小为0）。
因此都是用dp[m+1] [n+1]来标识str1[m]，str2[n]是否相等信息。
哦，好像是这样的哦，可是我还是有点迷糊。
没事儿，我画了张，你对照图看就能明白了。
文章插图
代码实现如下：
文章插图
你学会了吗，吒吒？
嗯，我看懂了哦，原来这么容易啊。
那你来总结下几种解法有什么区别吧？
嗯，第三种解法采取了动态规划的思想，解决的问题多数有重叠子问题这个特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
这样的话，复杂度就是O(m * n)，空间复杂度O(m * n)。
通过用空间换时间，使得字符串1与字符串2每个只是比较了一次！
那他和第一种、第二种解法又有什么不同呢？
他的执行效率优于第一种解法，而和第二种基于map定位的算法各有优劣。
当字符串重复率不高时而长度较长时，第二种算法（hash定位）时间和空间都优于第三种（动态规划）的算法。
当字符串中重复率逐渐升高时，第二种hash的算法效率明显下降，这时候，采用动态规划效率就更高。
不错啊，看来你完全掌握了哦，下次再教你一点新东西吧。
还是丙丙你教的好啊。好啊，下次我们再约！
推荐阅读
- 罗素：对平庸的崇拜是我们这个时代最大的恶之一
- 迁安发布暂停公共文化服务的通知
- 对中国疆域贡献最大的一个朝代，却不被后世所喜欢，惹易中天大骂
- 梁山天究星，挤掉孙立位置最大嫌疑人，宋江却看走了眼
- 省文化和旅游厅来我馆调研公共文化服务工作
- 封神榜他才是最大的受益者一家四口肉身成圣，还统领十万天兵！
- 做人最大的智慧，就是要认清自己，后半生才能活得明白
- 人性最大的善，是不让别人为难~经典分享
- 西天取经，谁付出的代价最大？小白龙看了看脖子！
- 晴雯与袭人：对你最大的欺骗，就是表面的岁月静好