求字符串的子序列是回文串的动态规划算法

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子1:
abcda
google
输出例子1:
2
2
这是腾讯2017暑期实习生的一道笔试题，在牛客网上做题时没有做出来，参考别人代码之后就我自己的理解与大家分享。
想法是这样的，既然是求删除字符个数的长度，我们转化为求最长公共子序列，然后返回原串和最长公共子序列的size之差就是要删除的字符个数。佷显然难点就在于求最长公共子序列。
我们以google这个字符串为例：
我们一眼可以看出它的最长公共子序列为goog。
我们根据回文串的定义可以先把原串逆置：elgoog。我要从中找出和原串相同的一段出来(每个字符可以不相连)。但我们不知道原串中的最长公共子序列到底是多长，所以我们要把原串中的每个字符都和逆置串的每个字符比较如果有相等的我们就加1，但是随之带来又一个问题:这个子串是和字符顺序有关的，我们可以借助一个二维数组正好可以利用横纵坐标来表示原串和子串，每个数组元素可以表示当前的最大公共子串。

MaxLen(i,j)表示s1左边i个字符与s2左边j个字符的最长公共子串长度

动态规划二维数组图

新手上路，程序来自牛客网该题的评论，如有不妥，请私聊。