金三银四，最近很多小伙伴都在寻找新的机会，经常会私聊一些算法题或者征求一些看法，老实说今年的环境没有前两年那么好，但是身边还是有不少小伙伴拿到大厂的offer。想进大厂，打铁还需自身硬。对于工程师，基本上都要写代码，而算法题，恰恰是大部分人难以逾越的，需要一定的积累与训练。今天我们来谈谈一个算法题，谈谈一种思想，动态规划。
题目
我们有一个连续的序列，每个序列上面都是一个数字c[i]，每次我们都能够消灭一个连续的回文子序列，消灭之后左右会合并，成为一个新序列，问最少需要多少次才能够把整个序列消灭掉。回文就是从左到有从右到左读到的序列都是一样的。
题目比较抽象，我们通过一些例子来说明这个问题吧？例如一开始的序列是1 4 4 2 3 2 1，那么我们最少需要2次，先消灭掉4 4 ， 然后再消灭调1 2 3 2 1.
第二个例子是 1 2 3 4 5 5 3 1，我们先消灭掉2 然后再消灭掉4， 最后消灭 1 3 5 5 3 1， 需要3次。
思考
这个题，我认为对于面试来说并不是一个好题，没有经过算法训练的人，即使提示也很难想到正确的思路。不过我们总不能跟面试官说这个题目不好吧，我们还是来思考下这个题目怎么解决。
这个题目，受过一定算法训练的人，就会一眼看出来是个动态规划，即使他可能找不出转移方程。，其实这是一种常见的动态规划的套路，区间动态规划。区间动态规划，最常用就是用f[i][j]表示一个区间，它可以由它的子区间推导出来。找出最优解的推导公式，一些都水到渠成。这个题目也是如此。
我们用f[i][j]表示消灭第i个数到第j个数总最少需要多少次。可以分为下面多种情况：
1.如果i等于j，也就是单个元素的时候，那么需要一次。
2.如果我们最左边的单独消灭，那么就是1+f[i+1][j],例如下面自序列 1 2 3 3 2, f[1,5] = f[1, 1] + f[2, 4]
3.第三种情况，我们可以找到一个跟c[i]一样的元素，然后把这个序列一份为二，结果为f[i][j] = f[i + 1][k - 1] + f[k + 1][j],这个可能比较抽象，这里面一个问题，我们先举个形象的例子，例如 1 2 3 3 2 1 7 7 9 9， 那么我们可以找到跟第一个元素相同的，也就是第6个元素， f[1][10] = f[2][5] + f[7][10], 这里有人可能会提问，那么这两个1为什么不用消除了呢？因为它可以跟着f[2][5]的最后一次消除消掉！
4. 对于第三种情况 一个最特殊的例子是 最前面的两位相同， 这个时候f[i + 1][k - 1]不存在！，所以f[i][j] =1 + f[i + 2][j],对应的例子就是 4 4 2 1 3
5.可能大家会有疑问，为什么要讨论把最左边的单读消灭，而不讨论最右边的单读消灭，假如最右边的单读消灭能够得到更有解，那么肯定存在于第三种情况。
综上所述，转移方程式如下：
总结
好了，现在我们需要写代码了，其实动态规划的题目，只要你找到转移方程了，就非常的简单，才去自下而上的方式进行编码。我们先枚举区间的长度，然后再进行枚举求职，talk is cheap, show me your code，下面是用go实现的代码。
