计科院20级刘磊

用户名：1579364808

访问量：4389

签　名：

写代码困了，就喝杯Java咖啡提提神

等　　级
排　　名	2497
经　　验	2278
参赛次数	6
文章发表	16
年　　龄	19
在职情况	学生
学　　校	怀化学院
专　　业	计算机科学与技术

　　自我简介：

计算机科学与技术专业的一名小码农

TA的其他文章

回溯法解决全排列
浏览：323

你可能喜欢

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

优质题解

最长公共子序列--动态规划

　　作者: 计科院20级刘磊　　　　发表时间：2021-10-05 15:18:42 浏览：256　|　评论：0　

原题链接：信息学奥赛一本通T1265- 最长公共子序列

###解题思路:
子序列的问题一般运用动态规划,又由于涉及到两个字符串,所以使用二维dp数组
确定了方法后就是经典的动归五部曲了:
- **明确dp数组的定义**:
dp[i][j] 以x[1~i]的字符串和以y[1~j]的字符串的LCS
- **确定状态转移方程**:
**依旧是数学归纳法的思想,假设dp[i-1][j-1],dp[i-1][j],dp[i][j-1]的结果已经出来,如何计算dp[i][j]呢?**很显然需要分x[i]和y[i]两个字符是否相等两种情况
**相等:**dp[i][j]=dp[i-1][j-1]+1;
**不相等:**dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);这里dp[i-1][j-1]其实可以省略,因为它不可能大于dp[i-1][j],dp[i][j-1]
- ** 确定base case**:
从递推公式来看需要初始化所有i或j为零的情况,即x,y字符串为空时的情况,此时显然为0
- **确定遍历顺序**:
dp[i][j]来自于以下三个方向,很显然是正向遍历
![](/image_editor_upload/20211005031644_40722.jpg)
- 打印dp数组

至此该题就解出来啦,上代码:

```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String x = input.nextLine();
        String y = input.nextLine();
        input.close();
        System.out.println(lengthOfLCS(x, y));
    }

public static int lengthOfLCS(String x, String y) {

int[][] dp = new int[x.length() + 1][y.length() + 1];   //以x[1~i]的字符串和以y[1~j]的字符串的LCS

for (int i = 1; i <= x.length(); i++) {
            for (int j = 1; j <= y.length(); j++) {
                if (x.charAt(i - 1) == y.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]);
                }
            }
        }
        return dp[x.length()][y.length()];
    }
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

最长公共子序列--动态规划

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

【绝对值排序】（C++代码）

回文数(一) （C语言代码）

P1001 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

最长公共子序列--动态规划

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

【绝对值排序】 （C++代码）

回文数(一) （C语言代码）

P1001 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

　　评论区

C语言训练-斐波纳契数列（C语言代码）

【绝对值排序】（C++代码）