leetcode 1143: 최대 공통 하위 시퀀스
1193 단어 알고리즘 문제 풀이
leetcode 1143: 최대 공통 하위 시퀀스
제목 설명: 두 개의 하위 서열의 가장 긴 공통 하위 서열을 구합니다
입력: text1 = "abcde",text2 = "ace"출력: 3 설명: 가장 긴 공통 서열은 "ace"이며 길이는 3 입니다.
문제풀이 단계: leetcode 516: 최장 회문 서열과 유사합니다.
1. 상태 정의: dp[i][j]에서 i는 문자열 1의 전 i 문자를 나타내고, j는 문자열 2의 전 j 문자를 나타내며, dp[i][j]는 s1[0...i]과 s2[0...j]의 가장 긴 공통 서열을 나타낸다.dp[len1+1][len2+1]
2. 상태 이동 방정식:
만약 s1[i]=s2[j]라면 이 문자는 가장 긴 공공 서열에 추가해야 합니다. dp[i][j]=dp[i-1][j-1]+1
하면, 만약, 만약...s2[j]는 dp[i][j]=max(dp[i-1][j], dp[i][j-1])
3. 초기화: dp[0][j]와 dp[i][0]는 모두 빈 문자열과 문자열 s의 공통 서열을 표시하고 길이는 0으로 설정한다.
4, 출력: dp[len1][len2]
코드:
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length()+1][text2.length()+1];
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
if(text1.charAt(i-1)==text2.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]);
}
}
}
for (int i = 0; i < dp.length; i++) {
System.out.println(Arrays.toString(dp[i]));
}
return dp[text1.length()][text2.length()];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vva1025- 알고리즘 입문 경전제목 링크https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3466분석이 dp[T][n]에서 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
