---

1.最长公共子序列

1.题目链接

• 最长公共子序列

---

2.算法原理详解

• 本题很重要，可以说是本子专题的模板题了
• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 选取第一个字符串[0, i]区间以及第二个字符串[0, j]区间作为研究对象
    • dp[i]j]：s1的[0, i]区间以及s2的[0, j]区间内所有的子序列中，最长公共子序列的长度

  • 推导状态转移方程：根据最后一个位置的情况，分情况讨论
    

  • 初始化：

    • 多开一行及一列虚拟结点
    • s1 = " " + s1, s2 = " " + s2 --> 便于下表对应

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

---

3.代码实现

int longestCommonSubsequence(string s1, string s2) 
{
    int n = s1.size(), m = s2.size();
    s1 = " " + s1, s2 = " " + s2;

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(s1[i] == s2[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];
}

---

2.不相交的线

1.题目链接

• 不相交的线

---

2.算法原理详解

• 分析：本题不相交的线，其实模型就是最长公共子序列，所以可以转化模型
• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • dp[i]j]：n1的[0, i]区间以及n2的[0, j]区间内所有的子序列中，最长公共子序列的长度

  • 推导状态转移方程：根据最后一个位置的情况，分情况讨论
    

  • 初始化：多开一行及一列虚拟结点

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

---

3.代码实现

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) 
{
    int n = nums1.size(), m = nums2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; 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]);
            }
        }
    }

    return dp[n][m];
}

---

3.不同的子序列

1.题目链接

• 不同的子序列

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • dp[i]j]：s的[0, j]区间内所有的子序列中，有多少个t的[0, i]区间的子串

  • 推导状态转移方程：根据s的子序列的最后一个位置包不包含s[j]

    • dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]
      

  • 初始化：

    • 多开一行及一列虚拟结点
    • 第一行初始化为1
    • 第一列初始化为0

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[m][n]

---

3.代码实现

int numDistinct(string s, string t) 
{
    const int MOD = 1e9 + 7;
    int n = s.size(), m = t.size();
    vector<vector<long long>> dp(m + 1, vector<long long>(n + 1));

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

    // DP
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] += dp[i][j - 1] % MOD;
            if(t[i - 1] == s[j - 1])
            {
                dp[i][j] += dp[i - 1][j - 1] % MOD;
            }
        }
    }

    return dp[m][n];
}

---

4.通配符匹配

1.题目链接

• 通配符匹配

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • dp[i]j]：p的[0, j]区间内的子串能否匹配s的[0, i]区间内的子串

  • 推导状态转移方程：根据最后一个位置的情况，分情况讨论

    • 本题若直接按照如下的状态转移方程去写，时间复杂度会到$O(N^3)$
    • 所以需要想办法优化
      

  • 优化：

    • 方法一：数学推导
      

    • 方法二：根据状态表示以及实际情况，优化状态转移方程 -> 抽象，难理解:(

      • 实际相当于保留了*，把状态传递给前面
        

  • 初始化：

    • 多开一行及一列虚拟结点
      ![[Pasted image 20240504212026.png]]

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

---

3.代码实现

bool isMatch(string s, string p) 
{
    int n = s.size(), m = p.size();
    s = " " + s, p = " " + p;
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));

    // Init
    dp[0][0] = true;
    for(int i = 1; i <= m; i++)
    {
        if(p[i] == '*')
        {
            dp[0][i] = true;
        }
        else
        {
            break;
        }
    }

    // DP
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(p[j] == '*')
            {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
            else
            {
                dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];
            }
        }
    }

    return dp[n][m];
}