专栏首页NLP小白的学习历程LCS(最长公共子序列问题)

LCS(最长公共子序列问题)

LCS(最长公共子序列问题)

首先,我们先声明一下子序列的概念:

取出序列中某些特定的项并保持它们在原来序列中的顺序,所得到的新序列成为原序列的子序列。

(所以说,子序列未必是连续的,连续的就叫子集了)

#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_N = 1000, MAX_M = 1000;
//输入
int n, m;
char s[MAX_N], t[MAX_M];

int dp[MAX_N + 1][MAX_M + 1];//DP数组

void solve()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (s[i] == t[j])
			{
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else
			{
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
			}
		}
	}
	cout << dp[n][m] << endl;
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> t[i];
	}
	memset(dp, 0, sizeof(dp));
	solve();
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 完全背包问题

    种花家的奋斗兔
  • 0-1背包问题(记忆化搜索与动态规划)(多种方法)

    函数解释:将s中当前位置后面的n个字节 (typedef unsigned int size_t )用 ch 替换并返回 s 。

    种花家的奋斗兔
  • 201604-2 试题名称: 俄罗斯方块

    注意:先分析问题,不要急着分类讨论,你可能分类讨论上百行还不如仔细分析后写几十行。

    种花家的奋斗兔
  • 算法训练 K好数

    问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = ...

    AI那点小事
  • P1387 最大正方形

    题目描述 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 输入输出格式 输入格式: 输入文件第一行为两个整数n,m(1<=n...

    attack
  • hdu1074

    @坤的
  • 【剑指Offer】60. n个骰子的点数

    使用一个二维数组 dp 存储点数出现的次数,其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

    瑞新
  • 完全背包问题

    种花家的奋斗兔
  • 【POJ 2923】Relocation(状压DP+DP)

    题意是给你n个物品,每次两辆车运,容量分别是c1,c2,求最少运送次数。 好像不是很好想,我看了网上的题解才做出来。 先用状压DP计算i状态下,第一辆可以运送的...

    饶文津
  • HDU-4539郑厂长系列故事——排兵布阵(状态压缩,动态规划)

    郑厂长系列故事——排兵布阵 Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65535/3276...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券