动态规划问题-LeetCode 5 (经典DP问题、LCS问题)

算法工程师之路

发布于 2019-09-17 10:24:27

2.3K00

代码可运行

文章被收录于专栏：算法工程师之路算法工程师之路

运行总次数：0

代码可运行

作者：TeddyZhang，公众号：算法工程师之路

DP基础问题：LeetCode #5

编程题

【LeetCode #5】最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。示例 2：输入: "cbbd" 输出: "bb"

解题思路：

前两天我们讲解了"中心拓展法"来解这道题目，今天我们使用动态规划的方法来写这道题目，首先我们要寻找一个递推式如下：我们将f[i][j]表述为从j到i的子串为回文串，j <= i，此时dp的矩阵为左下三角！如果a[i]==a[j]且f[i-1][j+1]=true, 那么f[i][j]也为true。

需要注意一点：当i-j < 2时，如果s[i]=s[j]，那么f[i][j]必为true，即单个字符或者两个相邻相同字符为回文子串。

C++代码为：

class Solution {
public:
    string longestPalindrome(string s) {
        int slen = s.length();
        if(slen == ) return "";
        string res = "";
        vector<vector<bool>> f(slen, vector<bool>(slen, false));
        int maxlen = ;
        int curlen = ;

        for(int i = ;i < slen; i++){
            for(int j = ;j <= i; j++){   // f[0][0]=true, 一定成立
                if((s[i] == s[j]) && ((i-j < ) || (i >  && f[i-1][j+]))){
                    f[i][j] = true;
                    curlen = i - j + ;
                    if(curlen > maxlen){
                        maxlen = curlen;
                        res = s.substr(j, curlen);
                    }
                }
            }
        }
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring

【经典动态规划】最长公共子序列

给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子序列，并返回其长度。 A = "Hello World" B = "loop" 则A与B的最长公共子序列为"loo"，返回最大长度为3.

注意：公共子序列不要求连续，而公共子串要求连续！

解题思路：

我们首先定义动态规划矩阵dp[i][j]为字符串A的第一个字符到第i个字符以及字符串B的第一个字符到第j个字符的最长公共子序列。比如A为"cake", B为"cat"，则dp[2][3]表示"ca"和"cat"之间的最长公共子序列！其中dp[0][2]表示""和"ca"的最长公共子序列，为零！因此我们可以得到递推式为：

其中，dp[i][0] = 0, dp[0][j] = 0.

class LCS
{
public:
    int findLCS(string A, int n, string B, int m)
    {
        if(n ==  || m == )//特殊输入
            return ;
        int dp[n + ][m + ];//定义状态数组
        for(int i =  ; i <= n; i++)//初始状态
            dp[i][] = ;
        for(int i = ; i <= m; i++)
            dp[][i] = ;
        for(int i = ; i <= n; i++)
            for(int j = ; j<= m; j++)
            {
                if(A[i - ] == B[j - ])//判断A的第i个字符和B的第j个字符是否相同
                    dp[i][j] = dp[i -1][j - ] + ;
                else
                    dp[i][j] = max(dp[i - ][j],dp[i][j - ]);
            }
            return dp[n][m];//最终的返回结果就是dp[n][m]
    }
};

【经典动态规划】最长公共子串

给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子串，并返回其长度。例如： A = "HelloWorld" B = "loop" 则A与B的最长公共子串为 "lo",返回的长度为2。

解题思路：

最长公共子串的问题不同于最长公共子序列，由于子串的连续的，而子序列不一定连续。在上一个子序列中dp[i][j]是非减的，因此最后返回最大公共子序列时，返回的是dp[n][m]。而在最大子串问题中，dp[i][j]可能小于dp[i-1][j-1]，因此需要一个res来保存更新最大值。

通俗考虑，在两个子串中寻找，假设a[i]==b[j]了，那么从i和j向后走，res会一直更新变大，一旦遇到不相等时，则dp[i][j]清零，寻找下一个重复的子串。因此其递推式为：

其中dp[i][0] = 0, dp[0][j] = 0;

C++代码：

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
         if(n ==  || m == )
            return ;
        int rs = ;
        int dp[n + ][m + ];
        for(int i =  ; i <= n; i++)//初始状态
            dp[i][] = ;
        for(int i = ; i <= m; i++)
            dp[][i] = ;
        for(int i = ; i <= n; i++)
            for(int j = ; j<= m; j++)
            {
                if(A[i - ] == B[j - ])
                {
                    dp[i][j] = dp[i -1][j - ] + ;
                    rs = max(rs,dp[i][j]);//每次更新记录最大值
                }

                else//不相等的情况
                    dp[i][j] = ;
            }
            return rs;//返回的结果为rs
    }
};