leetcode 72. 거리 편집(동적 계획)
2127 단어 동적 기획LeetCode20개의 동적 기획
두 단어의 워드1과 워드2를 정해 워드1을 워드2로 변환하는 데 사용되는 최소 조작수를 계산한다.
한 단어에 대해 다음 세 가지 작업을 수행할 수 있습니다.
: word1 = "horse", word2 = "ros"
: 3
:
horse -> rorse ( 'h' 'r')
rorse -> rose ( 'r')
rose -> ros ( 'e')
예2:
: word1 = "intention", word2 = "execution"
: 5
:
intention -> inention ( 't')
inention -> enention ( 'i' 'e')
enention -> exention ( 'n' 'x')
exention -> exection ( 'n' 'c')
exection -> execution ( 'u')
아이디어:
바꾸지 않고 간단하게 추가하고 삭제하면 가장 긴 공통 서열로 만들 수 있으며 가장 긴 공통 문자열을 찾은 다음len1+len2-2*공통 서열의 길이를 사용할 수 있습니다.
그러나 여기에 교체가 있고 교체가 있으면 상황이 달라진다. 왜냐하면 때때로 하나의 비례를 바꾸거나 두 개를 추가하거나 삭제하기 때문이다.
정의 상태: dp[i][j]: 첫 번째 열의 i번째 위치와 두 번째 열의 j번째 위치는 몇 번 조작해야 동일합니다.
이후에word1[i]=word2[j]가 같으면 바꿀 필요도 없고 삭제할 필요도 없다. 조작 횟수는 dp[i-1][j-1]과 직결된다.
만약 같지 않다면 세 가지 상황이 있다. 하나는 첫 번째 줄의 문자를 상태 dp[i-1][j]로 삭제하는 것이고, 두 번째는 두 번째 줄의 문자를 dp[i][j-1]로 삭제하는 것이며, 세 번째는 한 문자를 바꾸어 두 문자를 같게 하는 것이다.이 세 가지 조작은 모두 한 번만 진행한다.
그러면 전이 방정식은 dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])))+1이다.
잘못된 인식이 하나 있다. 만약에 긴 줄과 짧은 줄을 비교한다면 현재의 긴 줄만 삭제할 수 있다. 이런 인식은 잘못된 것이다. 예를 들어 다음과 같다.
sma와uism, 이 경우 짧은 문자열의 마지막 문자를 삭제해야 합니다. 이것은 sm의 일치에 방해가 되기 때문입니다.
상세 코드:
class Solution {
public:
int dp[1005][1005];
int minDistance(string word1, string word2) {
int len1 = word1.length();
int len2 = word2.length();
for(int i=0;i<=len1;i++)dp[i][0] = i;
for(int j=0;j<=len2;j++)dp[0][j] = j;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(word1[i-1]==word2[j-1])dp[i][j] = dp[i-1][j-1];
else {
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
return dp[len1][len2];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
