상용 알고리즘 정리: 동적 기획 중편

지난 장 에 서 는 동적 대화의 일부 Easy 와 Medium 어 려 운 문 제 를 다 루 었 는데 이런 문 제 를 풀 줄 안다 면 동적 계획 을 파악 한 것 은 말 할 것 도 없고 '피상 적' 이 라 고 할 수 밖 에 없다.
여기 서 우 리 는 몇 가지 더 복잡 한 동 규 문 제 를 고 르 는데 모두 Hard 어 려 운 문제 이 고 모두 이중 서열 문제 이다. 이런 문 제 를 bug free 까지 만 들 수 있어 야 동태 계획 을 기본적으로 파악 한 셈 이다.
첫 번 째 문제
제목 주소:https://leetcode.com/problems/edit-distance/ 대 의 는 한 단어 에 대해 최소한 의 조작 을 다른 단어 로 바 꾸 고 최소한 의 조작 횟수 를 구 하 는 것 이다.
문 제 를 먼저 분석 하고 왜 이 문 제 를 DP 로 풀 었 는 지.먼저 최소 조작 횟수 를 구 하 는 것 을 보 았 다. 이런 십중팔구 가 바로 DP 이다. 그 다음 에 문 제 를 분석 한 결과 이 문 제 를 몇 개의 작은 문제 로 분해 하여 풀 기 쉬 우 며 한 걸음 한 걸음 이 지난 결과 에 의존 하 는 것 을 발견 했다.
아니면 앞에서 말 한 두 가지 난점 에 대해:
1, dp [i] [j] 를 어떻게 정의 합 니까?
dp [i] [j] 우 리 는 두 가지 가장 흔히 볼 수 있 는 정의 가 있 습 니 다.

워드 1 의 0 ~ i 문자 가 워드 2 의 0 ~ j 문자 로 변 하 는 데 필요 한 최소 조작 횟수

워드 1 의 앞 i 문자 가 워드 2 의 앞 j 문자 로 변 하 는 데 필요 한 최소 조작 횟수

여기 서 우 리 는 두 번 째 정 의 를 선택 할 것 이다.사실 초기 값 은 한 글자 가 아니 라 한 글자 도 없 기 때문이다. 첫 번 째 정의 로 초기 값 0 이 첫 번 째 문 자 를 대표 한다 면 우 리 는 한 글자 도 없 는 상황 을 처리 하기 어렵다.그래서 우 리 는 두 번 째 정 의 를 선택한다.
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[i][j] = false;

또한 이 문 제 는 특히 초기 화 문제 에 주의해 야 하 며, 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/