상용 알고리즘 정리: 동적 기획 중편
Easy
와 Medium
어 려 운 문 제 를 다 루 었 는데 이런 문 제 를 풀 줄 안다 면 동적 계획 을 파악 한 것 은 말 할 것 도 없고 '피상 적' 이 라 고 할 수 밖 에 없다.여기 서 우 리 는 몇 가지 더 복잡 한 동 규 문 제 를 고 르 는데 모두
Hard
어 려 운 문제 이 고 모두 이중 서열 문제 이다. 이런 문 제 를 bug free 까지 만 들 수 있어 야 동태 계획 을 기본적으로 파악 한 셈 이다.첫 번 째 문제
제목 주소:https://leetcode.com/problems/edit-distance/ 대 의 는 한 단어 에 대해 최소한 의 조작 을 다른 단어 로 바 꾸 고 최소한 의 조작 횟수 를 구 하 는 것 이다.
문 제 를 먼저 분석 하고 왜 이 문 제 를 DP 로 풀 었 는 지.먼저 최소 조작 횟수 를 구 하 는 것 을 보 았 다. 이런 십중팔구 가 바로 DP 이다. 그 다음 에 문 제 를 분석 한 결과 이 문 제 를 몇 개의 작은 문제 로 분해 하여 풀 기 쉬 우 며 한 걸음 한 걸음 이 지난 결과 에 의존 하 는 것 을 발견 했다.
아니면 앞에서 말 한 두 가지 난점 에 대해:
1, dp [i] [j] 를 어떻게 정의 합 니까?
dp [i] [j] 우 리 는 두 가지 가장 흔히 볼 수 있 는 정의 가 있 습 니 다.
2, 어떻게 구 해
dp[i][j]
분명히 dp[i][[j]
앞의 결과 에 의존 하고 현재 word1[i]
와 word2[j]
가 같은 지 와 관련 이 있 으 므 로 우 리 는 상황 에 따라 토론 한다.word1[i-1] !== word2[j-1]
이런 상황 에서 우 리 는 세 가지 선택 을 할 수 있다. 워드 1 에서 i 번 째 를 삭제 하고 워드 2 에서 j 번 째 를 삭제 하거나 워드 1 [i] 을 워드 2 [j] 로 교체 하 는 것 이다. 이 세 가지 상황 은 모두 추가 적 인 조작 이 필요 하기 때문에 우 리 는 이 세 가지 상황 이 의존 하 는 전제조건 의 크기 를 비교 하면 된다. 즉, Math. min (dp [i - 1] [j], dp [i] [j - 1], dp [- 1], dp [- 1][j-1]) word1[i-1] === word2[j-1]
이런 상황 은 좀 간단 할 것 이다. 마지막 하 나 는 이미 같 기 때문에 추가 적 인 조작 이 필요 하지 않 기 때문에 사실은 dp [i - 1] [j - 1] 과 같다. i===0
과 j===0
의 상황 에 대해 초기 값 을 설정 하 는 것 입 니 다.전체 코드 는 다음 과 같 습 니 다:
var minDistance = function(word1, word2) {
var dp = [];
for(var i=0;i<=word1.length;i++) {
var row = [];
for(var j=0;j<=word2.length;j++) {
if(i===0) row.push(j);
else if(j===0) row.push(i);
else row.push(0);
}
dp.push(row);
}
for(i=1;i<=word1.length;i++) {
for(j=1;j<=word2.length;j++) {
if(word2[j-1] === word1[i-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1;
}
}
}
return dp[word1.length][word2.length];
};
같은 상황 에서
dp[i][j] = dp[i-1][j-1];
안심 하지 못 하 는 사람 도 있 을 수 있 습 니 다. 이것 이 가장 좋 은 것 이 아 닐 수도 있 습 니 다. 그러면 괜 찮 습 니 다. 여기 서도 여러 가지 상황 을 비교 해서 최소 치 를 취 할 수 있 습 니 다. 사실은 dp[i-1][j-1]
가 영원히 최소 치 라 는 것 을 알 수 있 습 니 다. 사실은 똑 같은 문자 두 개 에 대해 어떠한 조작 도 하지 않 는 것 이 가장 좋 은 방안 입 니 다.제2 문제
제목 주소:https://leetcode.com/problems/distinct-subsequences/ 전형 적 인 하위 서열 문 제 는 사실 지난 문제 와 비슷 하 다. 위의 문 제 를 통 해 알 수 있 듯 이 이런 두 서열 에 대한 문 제 는 기본적으로
dp[i][j]
의 정 의 는 i,j
가 아니 라 i, j
이다. 왜냐하면 우리 의 출발점 은 항상 원소 의 상황 이 없 기 때문이다. 0,0
사실은 두 서열 에 각각 하나의 요소 가 있다.그래서 이 문 제 는 우 리 는 여전히 이 정 의 를 따른다.
그러면 dp [i] [j] 를 어떻게 풀 어야 합 니까? 분명히 상황 에 따라 토론 해 야 합 니 다.
T[i-1] === S[j-1]
이런 상황 에서 두 가지 상황 으로 나 누 어 s [j] 와 S [j] 를 취하 지 않 으 면 왜 S [j] 를 취하 지 않 을 수 있 습 니까? j 앞 에 알파벳 과 T [i] 가 같 을 수 있 기 때 문 입 니 다. 두 가지 상황 은 각각 dp[i-1][j-1]
과 dp[i][j-1]
입 니 다. T[i-1] !== S[j-1]
한 가지 가능성 만 있 습 니 다. S [j], 즉 dp [i] [j - 1] 을 취하 지 않 습 니 다. var numDistinct = function(s, t) {
var dp = [];
for(var i=0;i<=t.length;i++) {
var row = [];
for(var j=0;j<=s.length;j++) {
if(i===0) row.push(1);
else row.push(0);
}
dp.push(row);
}
for(i=1;i<=t.length;i++) {
for(j=i;j<=s.length;j++) {
if(t[i-1] === s[j-1]) {
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[t.length][s.length];
};
제3 문제
이 문 제 는 언뜻 보기 에는 위의 두 글자 보다 어 려 울 것 입 니 다. 왜냐하면 그 는 세 개의 문자열 을 가지 고 있 기 때 문 입 니 다. 우 리 는 dp [i] [j] [k] 로 s1 의 앞 i 문자 와 s2 의 앞 j 문자 로 s3 의 앞 k 문 자 를 구성 해 야 합 니까? 그러면 시간 복잡 도가 O (n ^ 3) 로 직접 올 라 가 는 것 은 분명 안 됩 니 다. 자세히 보면 k = = i + j 이기 때문에 우 리 는 이렇게 정의 하면 됩 니 다.
dp [i] [j] 는 s1 의 앞 i 문자 와 s2 의 앞 j 문자 로 s3 의 앞 i + j 문 자 를 구성 합 니 다.
그러면 이 정 의 를 내 린 후에 우 리 는 dp [i] [j] 를 어떻게 풀 것 인가? 사실은 순서대로 교차 되 기 때문에 s3 의 마지막 문 자 는 s1 에서 오 거나 s2 에서 오 거나 상황 에 따라 토론 합 니 다.
s1[i-1] === s3[i+j-1] && s2[j-1] === s3[i+j-1]
쌍방의 마지막 문 자 는 모두 같 습 니 다. s3 의 마지막 문 자 는 s1 에서 찾 을 수도 있 고 s2 에서 찾 을 수도 있 습 니 다. 그러면 한 가지 상황 만 만족 하면 됩 니 다. dp [i] [j] = dp [i - 1] [j] | dp [i] [j - 1]; s1[i-1] === s3[i+j-1]
, s1 에서 만, dp [i] [j] = dp [i - 1] [j]; s2[i-1] === s3[i+j-1]
, s2 에서 만, dp [i] [j] = dp [i] [j - 1]; 또한 이 문 제 는 특히 초기 화 문제 에 주의해 야 하 며, dp [0] [j] 와 dp [i] [0] 의 초기 화 에 도 주의해 야 한다.
코드 는 다음 과 같 습 니 다:
var isInterleave = function(s1, s2, s3) {
if(s3.length !== (s1.length + s2.length)) return false;
if(s3.length === 0) return true;
var dp = [];
for(var i=0;i<=s1.length;i++) {
var row = [];
for(var j=0;j<=s2.length;j++) {
if(i===0) row.push(s2.slice(0,j) === s3.slice(0,i+j));
else if(j===0) row.push(s1.slice(0,i) === s3.slice(0,i+j));
else row.push(false);
}
dp.push(row);
}
for(i=1;i<=s1.length;i++) {
for(j=1;j<=s2.length;j++) {
if(s1[i-1] === s3[i+j-1] && s2[j-1] === s3[i+j-1]) {
dp[i][j] = dp[i-1][j] || dp[i][j-1];
} else if(s1[i-1] === s3[i+j-1]) {
dp[i][j] = dp[i-1][j];
} else if(s2[j-1] === s3[i+j-1]) {
dp[i][j] = dp[i][j-1];
} else {
dp[i][j] = false;
}
}
}
return dp[s1.length][s2.length];
};
두 배열 이 모두 hard 난이도 인 것 을 제외 하고 다음 장 에서 우 리 는 다른 몇 가지 hard 난이도 의 동 규 문 제 를 다시 이야기 합 니 다.
https://leetcode.com/problems/maximal-rectangle/
https://leetcode.com/problems/longest-valid-parentheses/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.