动态规划之子序列问题解题模板 :: labuladong的算法小抄

[labuladong]

文章链接点这里：动态规划之子序列问题解题模板

评论礼仪 见这里，违者直接拉黑。

[bert82503]

打卡，感谢楼主！

[bert82503]

自顶向下的带备忘录的递归解法。

dp 函数的定义是：在子串 s[i..j] 中，最长回文子序列的长度为 dp(s, i, j)。

Java版

class Solution {
    /**
     * 动态规划解题套路框架。
     * 提供我总结的一个思维框架，辅助你思考状态转移方程：
     * 明确 base case -> 明确「状态」 -> 明确「选择」 -> 定义 dp 数组/函数的含义。
     * 
     * 基本思路
     * 1、确定 base case。
     * 2、确定「状态」，也就是原问题和子问题中会变化的变量。
     * 3、确定「选择」，也就是导致「状态」产生变化的行为。
     * 4、明确 dp 函数/数组的定义。
     *
     * 自顶向下的带备忘录的递归解法
     */
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // 备忘录，初始化为 -1
        memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        
        // 整个 s 的最长回文子序列长度
        return dp(s, 0, n - 1);
    }

    // 备忘录
    int[][] memo;

    // dp 函数的定义是：在子串 s[i..j] 中，最长回文子序列的长度为 dp(s, i, j)。
    int dp(String s, int i, int j) {
        int n = s.length();
        if (i < 0 || i >= n || j < 0 || j >= n) {
            return 0;
        }
        // 查备忘录，防止重复计算
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 状态转移方程
        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = dp(s, i + 1, j - 1) + 1;
        } else {
            memo[i][j] = Math.max(
                dp(s, i + 1, j),
                dp(s, i, j - 1)
            );
        }
        return memo[i][j];
    }
}

[tljing]

可以转化为求和自己倒序序列的最长子序列

[LLLLLjian]

麻烦问一下 备忘录解法 为什么用的是 dp(s, i + 1, j - 1) + 1; 而不是 dp(s, i + 1, j - 1) + 2

[LLLLLjian]

贴一下我的理解 python版本

        class Solution:
            def longestPalindromeSubseq(self, s: str) -> int:
                if not s:
                    return 0
                length = len(s)
                # 备忘录
                # 字符串s在[i, j]范围内最长的回文子序列的长度为memo[i][j]
                memo = [[0] * length for _ in range(length)]
                def dp(i, j):
                    if (i<0) or (j<0) or (i>=length) or (j>=length) or (i>j):
                        # 越界情况
                        return 0
                    if i == j:
                        return 1
                    if memo[i][j]:
                        # 备忘录中有结果的话 使用备忘录
                        return memo[i][j]
                    # 开始条件判断
                    if s[i] == s[j]:
                        # 可以这么理解
                        # 假设有索引 i i+1 i+2 ..... j-1 j
                        # 如果s[i] == s[j], 那么 memo[i][j] = memo[i+1][j-1] + 2
                        memo[i][j] = dp(i+1, j-1) + 2
                    else:
                        memo[i][j] = max(
                            # 还可以这么理解
                            # 假设有索引 i i+1 i+2 ..... j-1 j
                            # 如果 s[i] != s[j], 那么 memo[i][j] = max(memo[i][j-1], memo[i+1][j])
                            # 加入s[i]
                            dp(i, j-1),
                            # 加入s[j]
                            dp(i+1, j)
                        )
                    return memo[i][j]
                return dp(0, length-1)

[yangpenghui111]

对啊为什么dp函数和dp数组，当i，j相同时一个加1 一个加2啊

[zhongweiLeex]

转化为传统的 i j 的下标， 这样判断回文比较直观

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        
        int[][] dp = new int[n][n];//dp[i][j]  s[i..j] 中最长回文子序列的长度

        for(int i = 0; i < n; i++){
            dp[i][i] = 1;
        }

        for(int len = 2 ; len<= n; len++){
            for(int i = 0; i+len - 1 < n ; i++){
                int j = i + len -1;
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;//向两边打开
                }else{
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}

[lhcezx]

让字符串成为回文串的最少插入次数，贴一个精简的从顶向下的C++。跟着东哥做了不少DP，感觉还是从顶向下带个备忘录更简单一点，有一些图的问题从base case出发自底向上更好

class Solution {
    vector<vector<int>> memo;
public:
    //  返回s[i, j] 变成回文串的最少插入次数
    int dp(string& s, int i, int j) {
        //  base case
        if (i >= j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (s[i] == s[j]) return memo[i][j] = dp(s, i + 1, j - 1);
        else return memo[i][j] = min(dp(s, i + 1, j), dp(s, i, j - 1)) + 1;
    }

    int minInsertions(string s) {
        int n = s.size();
        memo.assign(n, vector<int> (n, -1));
        return dp(s, 0, n - 1); 
    }
};

[guqihao-7]

楼上那位朋友这里这里加的是1

if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = dp(s, i + 1, j - 1) + 1;

这是因为他的base case设置的问题：

        int n = s.length();
        if (i < 0 || i >= n || j < 0 || j >= n) {
            return 0;
        }

实际上i不可能小于0，j也不可能在右边越界，所以base case相当于

        int n = s.length();
        if (i >= n || j < 0) {
            return 0;
        }

当i在右边越界，或者j在左边越界，其实相当于是把整个字符串走了两遍，因为实际上，只要i >= j时，整个字符串就已经走完，扫了一遍，所以memo[i][j] = dp(s, i + 1, j - 1) + 1;加一其实是2/2，或者这里也可以写成加二，但是最后返回的结果在除以二
但是需要注意不能在递归函数中除以二，而需要在调用递归函数的主函数除以二，代码被我简单修改后如下：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        // 在这里将结果除以2
        return dp(s, 0, n - 1) / 2;
    }

    int[][] memo;

    int dp(String s, int i, int j) {
        int n = s.length();
        if (i >= n || j < 0) {
            return 0;
        }

        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = dp(s, i + 1, j - 1) + 2;
        } else {
            memo[i][j] = Math.max(
                dp(s, i + 1, j),
                dp(s, i, j - 1)
            );
        }
        // 不能在这里将结果除以2
        return memo[i][j];
    }
}

但是实际上就像我上面说的，这个算法相当于扫了两边字符串，其实当i >= j时就可以停下，这个思路的java代码如下：

class Solution {
    public int longestPalindromeSubseq(String s) {
        memo = new int[s.length()][s.length()];
        for (int[] ints : memo) {
            Arrays.fill(ints, Integer.MIN_VALUE);
        }
        return process(s.toCharArray(), 0, s.length() - 1);
    }
    int[][] memo;
    public int process(char[] s, int left, int right) {
        if (left > right) {
            return 0;
        } else if (left == right) {
            return 1;
        }

        if (memo[left][right] != Integer.MIN_VALUE) {
            return memo[left][right];
        }

        if (s[left] == s[right]) {
            memo[left][right] = process(s, left + 1, right - 1) + 2;
        } else {
            memo[left][right] = Math.max(
                    process(s, left + 1, right),
                    process(s, left, right - 1)
            );
        }
        return memo[left][right];
    }
}

left就是上面的i，right就是上面的j，如果看不习惯可以自己改一下。需要说明的是left == right这种情况不能返回0，需要返回1，所以base case中多了一个 else if
这个写法和上面的一样，都是从左右两边向中间缩，区别就在于这个只扫了一遍字符串，所以在力扣提交时也能看到时间有差距

我自己在刚开始看这篇文章时，东哥没有给出备忘录解法，所以来看评论区，这里是加一，东哥那里是加二，导致我自己懵逼了很久，希望我这里能够帮到大家，使后来者不需要再踩坑。当然由于我水平有限可能会有一些错误，也希望大家能够指出

最后也想请教，这道题目的写法是否能够从中间往两侧扩？上面的写法都是从两侧往中间缩，自己水平有限尝试了很久也没写出来

[MzxlM]

1312 java dp 压缩版

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[] dp = new int[n];
        // int[][] dp = new int[n][n];
        // for(int i = 0; i < n; i++) {
        //     dp[i] = 1;
        //     // dp[i][i] = 1;
        // }
        for (int i = n-1; i >= 0; i--) {
            int pre = 0;
            for ( int j = i+1; j <n ; j++) {
                int temp = dp[j];
                if(s.charAt(i) == s.charAt(j)) {
                    dp[j] = pre;
                    // dp[i][j] = dp[i+1][j-1] +2;
                } else {
                    dp[j] = Math.min(dp[j], dp[j-1])+1;
                    // dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
                pre = temp;
            }
        }
        return dp[n-1];
    }
}

[lpdswing]

class Solution:
    def minInsertions(self, s: str) -> int:
        # 定义dp[i][j]为s[0..n-1]的最长回文长度
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        # base case
        for i in range(n):
            dp[i][i] = 1
        # 反向遍历,保证已知状态已经被求出
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return n - dp[0][n-1]

[bruceeewong]

打卡，最后那个把求最少插入次数变为回文串，一转为s长度-最长子序列长度，这脑筋太能急转弯了666

[EyeDroplyq]

提问： 让字符串成为回文串的最少插入次数的算法中。dp[i][j]=min(dp[i][j-1],dp[i+1[j])+1 为什么要加一啊，不太懂啊

[EyeDroplyq]

懂了

[newlifehaonan]

topdown + 备忘录 解 最长回文子序列

class Solution {
    String s;
    int[][] memo;

    public int longestPalindromeSubseq(String s) {
        this.s = s;
        int n = s.length();
        memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    memo[i][j] = 1;
                } else {
                    memo[i][j] = 0;
                }
            }
        }
        return dp(0,  n - 1);
    }

    public int dp(int i, int j) {
        // 状态: dp(i, j) 为 s[i....j] 最长回文子序列的长度
        // i = j 时: memo[i][j] = 1
        // i > j 时: memo[i][j] = 0
        // return dp(0, s.length - 1);
        // 状态转移方程:
        // s[i] = s[j] dp(i, j) = dp(i + 1, j -1) + 2;
        // s[i] != s[j] dp(i, j) = Max(dp(i + 1, j), dp(i, j -1))
        if (i >= j) return memo[i][j];
        if ( i < j && memo[i][j] != 0) return memo[i][j];
        if (s.charAt(i) == s.charAt(j)) {
            memo[i][j] = dp(i + 1, j - 1) + 2;
        } else {
            memo[i][j] = Math.max(
                dp(i + 1, j),
                dp(i, j - 1)
            );
        }
        return memo[i][j];
    }
}