动态规划 最长公共字符子序列

问题

求两字符序列的最长公共字符子序列

解答

说起动态规划，又得说他的递推公式。往往这个公式并不好一眼看出，需要找规律，这就是我们需要攻克的地方。我的思路是先做图表。在不断画图的过程中去寻找规律。

画图

画图的过程其实就是一个解读题目的过程。重点就是如何设置横坐标和纵坐标。子序列的问题，当然就是字母。

例如下面abc和bcd

先看第一行。其实表示的就是b在a,ab,abc的子序列结果。x在往后的过程，是需要前面的结果做比较的，取最大的那个。

现在考虑第二行

第二行就有所不同了。表示的是bc在a,ab,abc的子序列。填写ac的时候其实就考虑b的值与c自己的匹配情况就好。ab是0，c与a也不匹配，那么只能结果是0。bc的情况需要考虑a与bc的匹配情况，以及b与ab的匹配情况，以及c自身的匹配情况。相比之下最大的就是1（比较的是bb,ac框中的内容），cc的情况也一样，但是比较是相同的，相同的情况就需要看看没有c的情况，就是ab和b的比较情况，多了一个字符命中，就需要把都少一个情况的结果累计上。相比之下就是2。

第三行其实和第二行的比较类似。

d没有命中任何字符串。所以一直到cd的时候，结果还是2。字符串比较完毕。

代码实现参考

总结

动态规划是有递推公式的。但是这个公式可以没必要显示的写出，靠在画图的过程中寻找规律也可以做到。