LeetCode热题100刷题13：64. 最小路径和、62. 不同路径、5. 最长回文子串、1143. 最长公共子序列

64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,INT_MAX));
        dp[0][0]=grid[0][0];
        if(m==1 && n==1)
            return grid[0][0];
        for(int i=1;i<m;i++) {
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++) {
            dp[0][j] = dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];

    }
};

62. 不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<m;i++) 
            dp[i][0] = 1;
        for(int j=0;j<n;j++) 
            dp[0][j] = 1;
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size()));
        string res;
        int max_length=1;
        int start = 0;
        for(int i=0;i<s.size();i++) {
            for(int j=i;j>=0;j--) {
                if(i==j)
                    dp[j][i]=1;
                else if(i==j+1) {
                    dp[j][i]=(s[i]==s[j]);
                }else {
                    dp[j][i]=(s[i]==s[j])&&dp[j+1][i-1];
                }
                if(dp[j][i] && (i-j+1)>max_length) {
                    max_length = i-j+1;
                    start=j;
                }
            }
        }
        return s.substr(start,max_length);
    }
};

1143. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int length1 = text1.size();
        int length2 = text2.size();

        vector<vector<int>> dp(length1+1, vector<int>(length2+1,0));

        int res = 0;
        for(int i=1;i<=length1;i++) {
            for(int j=1;j<=length2;j++) {
                if(text1[i-1] != text2[j-1]) {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
                else {
                    dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]);
                }
                res = max(res,dp[i][j]);
            }
        }
        return res;
    }
};