动态规划问题(三)

一、 最长公共子串

解法一:枚举

• 我们完全可以遍历两个字符串的所有字符串作为起始
• 然后同时开始检查字符是否相等，相等则不断后移，增加子串长度，如果不等说明以这两个为起点的子串截止了，不会再有了。
• 后续比较长度维护最大值即可。

class Solution {
    
public:
    string LCS(string str1, string str2) {
    
        int length = 0;
        string res = ""; 
        //遍历s1每个起始点
        for(int i = 0; i < str1.length(); i++){
     
            //遍历s2每个起点
            for(int j = 0; j < str2.length(); j++){
     
                int temp = 0;
                string temps = "";
                int x = i, y = j;
                //比较每个起点为始的子串
                while(x < str1.length() && y < str2.length() && str1[x] == str2[y]){
     
                    temps += str1[x];
                    x++;
                    y++;
                    temp++;
                }
                //更新更大的长度子串
                if(length < temp){
     
                    length = temp;
                    res = temps;
                }
            }
        }
        return res;
    }
};

超时，测试用例不能完全通过
时间复杂度：O(m^2*n)其中mmm是str1的长度，n是str2的长度，分别枚举两个字符串每个字符作为起点，后续检查子串长度最坏需要花费O(m)
空间复杂度：O(n)，res属于返回必要空间，temps属于临时辅助空间，最坏情况下长度为n

解法二:动态规划(推荐)

• 我们可以用dp[i][j]在str1中以第iii个字符结尾在str2中以第jjj个字符结尾时的公共子串长度，
• 遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，dp[i][j]=dp[i−1][j−1]+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
• 每次更新dp[i][j]后，我们维护最大值，并更新该子串结束位置。
• 最后根据最大值结束位置即可截取出子串。

class Solution {
    
public:
    string LCS(string str1, string str2) {
    
        //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
        vector<vector<int> > dp(str1.length() + 1, vector<int>(str2.length() + 1, 0)); 
        int max = 0;
        int pos = 0;
        for(int i = 1; i <= str1.length(); i++){
    
            for(int j = 1; j <= str2.length(); j++){
    
                //如果该两位相同
                if(str1[i - 1] == str2[j - 1]){
     
                    //则增加长度
                    dp[i][j] = dp[i - 1][j - 1] + 1; 
                }
                else{
     
                    //该位置为0
                    dp[i][j] = 0; 
                }
                //更新最大长度
                if(dp[i][j] > max){
     
                    max = dp[i][j];
                    pos = i - 1;
                }
            }
        }
        return str1.substr(pos - max + 1, max);
    }
};

时间复杂度：O(mn)，其中m是str1的长度，n是str2的长度，遍历两个字符串所有字符
空间复杂度：O(mn)，dp数组大小为m∗n

二、不同路径的数目(一)

解法一:递归

首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个(n−1)∗m的矩阵中查找从左上角到右下角的不同路径数；而如果向下走，相当于后面在一个n∗(m−1)的矩阵中查找从左上角到右下角不同的路径数。而(n−1)∗m的矩阵与n∗(m−1)的矩阵都是n∗m矩阵的子问题，因此可以使用递归。

• 当矩阵变长n减少到1的时候，很明显只能往下走，没有别的选择了，只有1条路径；同理m减少到1时也是如此。因此此时返回数量为1.
• 对于每一级都将其两个子问题返回的结果相加返回给上一级。
• 每一级都有向下或者向右两种路径选择，分别进入相应分支的子问题。

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        //矩阵只要有一条边为1，路径数就只有一种了
        if(m == 1 || n == 1) 
            return 1;
        //两个分支
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); 
    }
};

时间复杂度：O(m*n)，其中m、n分别为矩阵的两边长，递归过程对于每个m最多都要经过每一种n
空间复杂度：O(m+n)，递归栈的最大深度为矩阵两边从m、n都到了1

解法二:动态规划(推荐)

• 用dp[i][j]表示大小为i∗j的矩阵的路径数量，下标从1开始。
• 当i或者j为1的时候，代表矩阵只有一行或者一列，因此只有一种路径。
• 每个格子的路径数只会来自它左边的格子数和上边的格子数，因此状态转移为dp[i][j]=dp[i−1][j]+dp[i][j−1]
  

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        //dp[i][j]表示大小为i*j的矩阵的路径数量
        vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0)); 
        for(int i = 1; i <= m; i++){
    
            for(int j = 1; j <= n; j++){
    
                //只有1行的时候，只有一种路径
                if(i == 1){
     
                    dp[i][j] = 1;
                    continue;
                }
                //只有1列的时候，只有一种路径
                if(j == 1){
     
                    dp[i][j] = 1;
                    continue;
                }
                //路径数等于左方格子的路径数加上上方格子的路径数
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 
            }
        }
        return dp[m][n];
    }
};

时间复杂度：O(mn)，其中m、n分别为矩阵的两边长，两层遍历填充整个dp数组
空间复杂度：O(mn)，辅助空间dp数组为二维数组

解法三:组合数学

从矩阵左上角走到矩阵右下角，总共需要往下走m−11步，往右走n−1步，不同的走法路径在于往下和往右的组合情况，即在一堆往下和往右的序列中，每种排列的情况，序列一共有m+n−2个位置，选择其中n−1个位置作为往下，即不同的走法有
种情况

• 分子分母从1开始
• 按照公式累乘相除

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        //防止溢出
        long res = 1; 
        for(int i = 1; i < n; i++)
            //根据公式计算
            res = res * (m + i - 1) / i; 
        return (int)res;
    }
};

时间复杂度：O(n)，计算过程需要从1遍历到n
空间复杂度：O(1)，常数级变量，无额外辅助空间