vlambda
2020-07-07

字节跳动的一道动态规划面试题

最近公司大量招人，发动了大家的力量。我也跟着一起下载了脉脉，脉脉上好多HR在招人。碰巧看见了一个猎头的动态，说这就是字节的算法面试题，你能做对几道？我大概扫了一眼，考察深度优先搜索（DFS），链表的题目不在少数，动态规划的题目也特别醒目。对DFS，链表相关题目感兴趣的可以看我之前的文章。正好我们昨天在聊动态规划的爬楼梯问题，今天我们也就来聊聊字节面试题中的最长回文子序列问题。

题目是这样的：给定一个序列，找到其中最长的回文子序列，并返回该序列的长度。对于一个回文子序列来说，正着读跟倒着读都一样。我们对子序列的定义是，它可以由其它序列删除一些元素或者不删得到，不影响剩余的元素的顺序。

示例 1:

输入:
"abdbca"
输出:
5
一个可能的最长回文子序列为 "abdba"。

示例 2:

输入:
"cddpd"
输出:
3
一个可能的最长回文子序列为 "ddd"。

基本思路

最直接最暴力的方式还是递归出它所有的子序列就好了嘛！虽然这一听就不是太好的主意。😄我们可以从输入序列的首尾两端开始，每一步，我们有两个情况：

如果首尾两端相同，我们的结果就会＋２，然后对剩余的序列做递归。
如果不同那我们跳过首端或者尾端对剩余的序列做递归。

如果我们遇到的是情况１的话，会给我们最长子序列的长度。而在情况２下最长子序列的长度由两个递归调用的最大值产生。

理清楚这个逻辑后，代码就很容易写出来了：

public int findLPSLength(String st) {
        return findLPSLengthRecursive(st, 0, st.length() - 1);
    }

    private int findLPSLengthRecursive(String st, int startIndex, int endIndex) {
        if (startIndex > endIndex)
            return 0;

        // 只有一个元素的序列就是一个长度为1的回文子串
        if (startIndex == endIndex)
            return 1;

        // 情况1，首尾相等
        if (st.charAt(startIndex) == st.charAt(endIndex))
            return 2 + findLPSLengthRecursive(st, startIndex + 1, endIndex - 1);

        //情况2，跳过首尾中的一个
        int c1 = findLPSLengthRecursive(st, startIndex + 1, endIndex);
        int c2 = findLPSLengthRecursive(st, startIndex, endIndex - 1);
        return Math.max(c1, c2);
    }

代码不复杂，短短几行，但是复杂度不低。😂时间复杂度达到了Ｏ(2^n)，ｎ是输入序列的长度，这里的空间复杂度是O(n)。

没关系，我们再来用我们擅长的缓存来优化。

自上而下

我们来用一个数组去保存已经解决过的子问题。对于我们的递归函数来说，变化的值就是我们传入的首尾两个索引值，所以我们可以把结果保存在一个二维数组里面，当然了，你愿意的话，也可以用哈希表。

加上缓存只需要改动几行代码：

 public int findLPSLength(String st) {
        Integer[][] dp = new Integer[st.length()][st.length()];
        return findLPSLengthRecursive(dp, st, 0, st.length()-1);
    }

    private int findLPSLengthRecursive(Integer[][] dp, String st, int startIndex, int endIndex) {
        if(startIndex > endIndex)
            return 0;

        //只有一个元素的序列就是一个长度为1的回文子串
        if(startIndex == endIndex)
            return 1;

        if(dp[startIndex][endIndex] == null) {
            //情况1，首尾相等
            if(st.charAt(startIndex) == st.charAt(endIndex)) {
                dp[startIndex][endIndex] = 2 + findLPSLengthRecursive(dp, st, startIndex+1, endIndex-1);
            } else {
                // 情况2，跳过首尾中的一个
                int c1 =  findLPSLengthRecursive(dp, st, startIndex+1, endIndex);
                int c2 =  findLPSLengthRecursive(dp, st, startIndex, endIndex-1);
                dp[startIndex][endIndex] = Math.max(c1, c2);
            }
        }

        return dp[startIndex][endIndex];
    }

我们的复杂度有木有得到优化？我们现在用一个二维数组缓存了子问题的结果，dp[st.length()][st.length()]，也就是说，我们不会有超过n*n的子问题，n是输入序列的长度，这意味着我们的时间复杂度是O(n^2)。而我们的空间复杂度也因为数组的开销变成了O(n^2)，没关系，空间换时间嘛，很正常。

自下而上

我们是想尝试给定序列的所有子序列，我们还是用二维数组来存储我们的结果。我们可以从给定序列的开头开始，一次加入一个元素。在每一步，我们都会尝试它的所有子序列。那在这个序列上，我们有两个选择：

如果在 startIndex 上的元素跟 endIndex上的元素匹配，那么最大长度就是2+startIndex+1 到endIndex-1之间的最大长度。

如果在 startIndex 的元素跟 endIndex不匹配, 我们将通过跳过在 startIndex或者 endIndex的元素来获取最大长度。

那我们的方程式就变成：

if (st[endIndex] == st[startIndex]){
   dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1]
} else{
   dp[startIndex][endIndex] = Math.max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1])}

那其实就是我们要想办法从最短的序列开始计算，才能计算出从开头到末尾，最大的回文子序列是多长。

我们还是拿上面‘cddpd’的例子来画一张图看一下：

每个单个元素都是一个长度为1的回文子序列。

startIndex:3, endIndex:4 => st[startIndex] !=st[endIndex], 所以dp[startIndex][endIndex] = max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1])

startIndex:2, endIndex:3 => st[startIndex] !=st[endIndex], 所以dp[startIndex][endIndex] = max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1])

startIndex:2, endIndex:4 => st[startIndex] ==st[endIndex], 所以dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1]
以此类推，我们最终的结果是：

根据这张图，我们可以清晰看到，最长子序列是dp[0][4]，也就是3。

那思路也梳理到这个地步了，我们可以把代码写一写了：

public int findLPSLength(String st) {
        // dp[i][j]存储着从i到j的最长子序列
        int[][] dp = new int[st.length()][st.length()];

        //每个单独的元素都是长度为1的回文子序列
        for (int i = 0; i < st.length(); i++)
            dp[i][i] = 1;

        for (int startIndex = st.length() - 1; startIndex >= 0; startIndex--) {
            for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {
                //情况1，首尾相同
                if (st.charAt(startIndex) == st.charAt(endIndex)) {
                    dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1];
                } else { //情况2，跳过首尾中的一个
                    dp[startIndex][endIndex] = Math.max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1]);
                }
            }
        }
        return dp[0][st.length() - 1];
    }