[DP]9251号-LCS(日付45)
9329 ワード
#include <iostream>
//memset 사용
#include <cstring>
//max, max_element 사용
#include <algorithm>
using namespace std;
int main(){
//두 문자열 입력
string l1;
string l2;
cin >> l1;
cin >> l2;
//두 문자열 길이 입력
int n = l1.size();
int m = l2.size();
//2차원 배열 dp 동적 할당
int ** dp = new int *[n+1];
for (int i=0; i<n+1; i++){
dp[i] = new int[m+1];
memset(dp[i], 0, sizeof(int)*(m+1));
}
//첫문자부터 끝까지
for(int i=1; i<n+1; i++){
for(int j=1; j<m+1; j++){
//l1과 l2의 문자가 같을 때
if(l1[i-1] == l2[j-1]){
//l1의 직전&l2의 현재, l1의 현재&l2의 직전, l1의 직전&l2의 직전+1 중 가장 큰 길이를 저장
dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1});
}
//l1과 l2의 문자가 다를 때
else{
//l1의 직전&l2의 현재, l1의 현재&l2의 직전, l1의 직전&l2의 직전 중 가장 큰 길이를 저장
dp[i][j] = max({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]});
}
}
}
//마지막까지 탐색 이후 가장 긴 길이 출력
cout << dp[n][m];
}
Reference
この問題について([DP]9251号-LCS(日付45)), 我々は、より多くの情報をここで見つけました https://velog.io/@bobsiunn/DP-9251번-LCS44일차テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol