DP：最长公共子序列Ⅰ

╰+攻爆jí腚メ 2023-10-06 20:44 4阅读 0赞

## DP：最长公共子序列Ⅰ ##

#### 文章目录 ####

*  DP：最长公共子序列Ⅰ
 *   *   *  问题
         *  思路
         *  代码

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路 ####

我们先从最简单的情况入手，设两个字符串为A，B，如果只看两个串的前1个字符，那么如果A\[1\]等于B\[1\]，最长公共子序列为1；如果A\[1\]不等于B\[1\]，最长公共子序列为0。如果只看前2个字符，如果A\[2\]等于B\[2\]，最长公共子序列长度是否等于之前只看前1个字符时的答案+1呢？一个公共子序列一定包含在从第一个字符开始的某个连续序列中，而不同连续序列以不同位置的字符结尾，如果用DP\[i\]表示两个串前i个字符以第i个字符结尾的最长公共子序列的长度，那么有`DP[i]=max{DP[j],j=1~i-1}+(A[i]==B[i])`吗？实际上我们不能用这个状态转移方程解题，使用该方程的前提是：两个字符串中连续序列以同一位置i的字符结尾，也就是所判断的两个连续序列是位置对应长度相同的，但题目中并没有要求这一点，公共子序列可以出现在两个字符串的不同连续序列中，再来看看最开始的例子，我们并没有考虑到A\[2\] = B\[1\] 或 B\[2\] = A\[1\]的情况，也就是说，使用一维dp数组表达不出所有的状态。  
  为了表示公共子序列处于两个字符串长度不同的连续序列中，我们需要用二维dp数组来表示所有的状态。我们用DP\[ i \] \[ j \]表示A\[1 ~ i\] 与 B\[1 ~ j\]的最长公共子序列的长度，若A\[i\]==B\[j\]，则DP\[i\] \[j\]由DP\[i - 1\] \[j - 1\] + 1转移得到，若不等，则DP\[i - 1\] \[j - 1\]由Max(DP\[i - 1\]\[j\]，DP\[i\]\[j - 1\])转移得到，注意不等的情况并不是继承DP\[i - 1\] \[j - 1\]，因为A\[i\]虽不等于B\[j\]，但A\[i\]可能与B\[1 ~ j - 1\]包含的子序列中最后一个元素相等，同理，B\[j\]可能与A\[1 ~ i - 1\]包含的子序列中最后一个元素相等。  
  所以状态转移方程为：  
![在这里插入图片描述][2c53fc277d4a4b1c8b73cfa0ee581c0e.png]  
  初始状态DP\[0\]\[0\]表示两个空串的最长公共子序列，即为0。

#### 代码 ####

import java.util.*;
    
    public class Main {
        
        static int[][] dp = new int[1005][1005];
        public static void main(String[] args) {
        
            StringBuilder str1 = new StringBuilder();
            StringBuilder str2 = new StringBuilder();
            int i, j, ans;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()) {
        
                ans = 0;
                str1.delete(0, str1.length());
                str1.append(scanner.next());
                str2.delete(0, str2.length());
                str2.append(scanner.next());
                dp[0][0] = 0;
                for (i = 1;i <= str1.length();i++) {
        
                    for (j = 1;j <= str2.length();j++) {
        
                        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
        
                            dp[i][j] = dp[i - 1][j - 1] + 1;
                        } else {
        
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                        }
                        ans = Math.max(ans, dp[i][j]);
                    }
                }
                System.out.println(ans);
            }
        }
    }

代码中除初始化dp\[0\]\[0\] = 0外，无需做其他重置或初始化工作，因为双循环变量都是从1开始，dp\[0\]\[\]和dp\[\]\[0\]一直等于0，不会被赋值，dp数组填充也是从前向后遍历，当前测试样例不会受前一个测试样例造成的脏数据影响

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/37927c767c4f459e9e9b71b78ee69207.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/746b23af879e48f1b609230e51ac460c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[2c53fc277d4a4b1c8b73cfa0ee581c0e.png]: https://img-blog.csdnimg.cn/2c53fc277d4a4b1c8b73cfa0ee581c0e.png