动态规划算法专题四--两个数组dp问题

目录

题四十 最长公共子序列

 题四十一 不相交的线

 题四十二 不同子序列

 题四十三 通配符匹配

---

题四十 最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

题解：

状态方程：dp[i][j]：表示s1字符串[0,i]区间和s2字符串[0,j]区间，最长公共子序列。

根据方程进行推导：分两种情况讨论当s1[i] == s2[j] / s1[i] != s2[j]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //1、创建dp表
        int n = text1.size();
        int m = text2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
 
        //2、初始化
        text1 = " " + text1;
        text2 = " " + text2;
 
        //3、填表
        for(int i = 1; i<n+1; ++i)
        {
            for(int j = 1; j<m+1; ++j)
            {
                if(text1[i] == text2[j])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
 
        //返回值
        return dp[n][m];
 
    }
};

 题四十一 不相交的线

1035. 不相交的线 - 力扣（LeetCode）

题解：

状态方程：dp[i][j]：nums1序列[0,i]区间和nums2序列[0,j]区间，有多少个不相交线。

根据方程进行推导：分两种情况讨论当s1[i] == s2[j] / s1[i] != s2[j]

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        //1、创建dp表
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m+1, vector<int> (n+1));
 
        //2、初始化
 
        //3、填表
        for(int i = 1; i<m+1; ++i)
        {
            for(int j = 1; j<n+1; ++j)
            {
                if(nums1[i-1] == nums2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
 
        //4、返回值
        return dp[m][n];
 
 
 
 
    }
};    
 
 
 

 题四十二 不同子序列

LCR 097. 不同的子序列 - 力扣（LeetCode）

题解：

dp[i][j]：表示[0,i]区间的s串，有多少个[0,j]区间的t串。

根据此状态方程推导。

class Solution {
public:
    int numDistinct(string s, string t) {
        //1、创建dp表
        int m = s.size();
        int n = t. size();
        vector<vector<double>> dp(m+1, vector<double> (n+1));
 
        //2、初始化
        for(int i = 0; i<m+1; ++i)
        {
            dp[i][0] = 1;
        }
 
        //3、填表
        for(int i = 1; i<m+1; ++i)
        {
            for(int j = 1; j<n+1; ++j)
            {
                dp[i][j] += dp[i-1][j];
                if(s[i-1] == t[j-1])
                {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
 
        //4、返回值
        return dp[m][n];
        
    }
};

 题四十三 通配符匹配

44. 通配符匹配 - 力扣（LeetCode）

题解：

dp[i][j]：表示[0,i]区间的s串，有多少个[0,j]区间的t串。

根据此状态方程推导。