算法入门学习基础之LCS篇

1.处理字符所需要的编辑次数

**方法：**我们可以通过构建一个二位数组，来存储我们的编辑次数，编辑的方式只有三种：增 删 替换
例如我有两个字符串s和s1，s=hello s1=halo 我把它横向铺开变成以下形式：
h e l l o
h a l o
我总共经历了两个变化 替换和删除 下面我们引入数组来表示这一过程

这张图片是怎样来的呢？
我们假设这个数组名叫做edit[x][y],从edit[0][0]开始，我们从上至下进行处理，若这个位置所对应的两个字母相等，则返回它左边，上边和右左的最小值min，若这个位置所对应的两个字母不相等，则返回它左边，上边和右左的最小值min+1，最终在最右下角的那个数值就等于我对这个字符的总编辑次数。

2.寻找两个字符串中的LCS

构建一个二维数组，用来记录数据的变化形式，数字代表x【i】和y【j】的最大LCS
箭头代表这个的变化趋势，只有当x【i】= y【j】时数字加1，从左上角的数字加1，其余的数字是根据左边和上边的最小值来确定的。最后通过找到箭头位置来确定这个LCS是什么，通过cout打印出来

二维数组的形式如下

最红通过类的方式进行打印数据，源代码如图

最终可以快速的得到这两个字符串的LCS是什么