LetCode 문제풀이 방법 5 - 동적 계획 거리 구하기 문제

1. 제목 번호
?-단순 거리 문제 72 - 거리 편집(어려움)
2. 방법 설명
동적 기획 사상을 채택하여 전이 방정식 dp[i][j]=?를 구한다.
3. 단순 거리 문제
제목:
출처: 리코더 링크:https://leetcode-cn.com/problems/regular-expression-matching저작권은 인터넷 소유에 귀속된다.상업 전재는 관공서에 연락하여 권한을 수여하고 비상업 전재는 출처를 밝혀 주십시오.
코드

bool isMatch(char * s, char * p){
    int i, j, len1, len2;
    len1 = strlen(s);
    len2 = strlen(p);
    bool** dp;
    dp = (bool**)malloc(sizeof(bool*) * (len1 + 1));
    for (i = 0; i < len1 + 1; i++) {
        dp[i] = (bool*)malloc(sizeof(bool) * (len2 + 1));
        memset(dp[i], 0, sizeof(bool) * (len2 + 1));
    }
    dp[0][0] = true;
    for (i = 0; i < len2; i++) {
        if (p[i] == '*' && i > 0 && dp[0][i - 1]) {
            dp[0][i + 1] = true;
        }
    }
    for (i = 0; i < len1; i++) {
        for (j = 0; j < len2; j++) {
            if (s[i] == p[j] || p[j] == '.') {
                dp[i + 1][j + 1] = dp[i][j];
                continue;
            }
            if (p[j] == '*' && j > 0) {
                if (s[i] == p[j - 1] || p[j - 1] == '.') {
                    dp[i + 1][j + 1] = dp[i][j + 1] || dp[i][j - 1] || dp[i + 1][j - 1];
                } else {
                    dp[i + 1][j + 1] = dp[i + 1][j - 1];
                }
            }
        }
    }
    return dp[len1][len2];
}

4.72 문항 편집 거리
제목은 두 단어의 워드1과 워드2를 정해 워드1을 워드2로 바꾸는 데 사용되는 최소 조작수를 계산한다.
한 단어에 대해 다음 세 가지 작업을 수행할 수 있습니다.
문자 삽입 삭제 문자 교체 예1:
입력: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'삽입)
출처: 리코더 링크:https://leetcode-cn.com/problems/edit-distance저작권은 인터넷 소유에 귀속된다.상업 전재는 관공서에 연락하여 권한을 수여하고 비상업 전재는 출처를 밝혀 주십시오.사고방식은 이 문제를 거슬러 올라가는 방법으로 시간을 초과하기 때문에 동태적으로 기획하는 방법만 사용할 수 있다.먼저 복잡한 문제를 간단하게 하고 dp[i][j]로 문자열word1의 1~i를 표시하며 문자열word2의 1~j로 바꾸는 데 최소한 몇 걸음이 걸린다.[i][j][j]의 계산 방법은 dp[i-1][j-1], dp[i][j][j][j][j]에 따라 dp[i-1][j], dp[i-1][j-1]가 x일 경우 워드2 길이 j-1이 j로 변할 때 워드2 길이 j-1이 j로 변하여 워드1이 j로 변하여 워드1이 word2로 변하기 때문에 삽입을 한 번 더 해야 하고 횟수가 x+1으로 변하여 dp[i-1][i-1][i-1] [j][j]로 변하면 dp[j]의 계산 방법은 dp[j]에 따라 계산방법은 dp[i-1[i-1[i-1][i-1]에 따라 계산방법은 dp[i-1[i-1[i-1]에 따라 계산할 수 있다. dp[i-[j]에 따라 계산j],word1이 word2로 변하면 변화 횟수를 늘릴 필요가 없습니다. 횟수는 x입니다. dp[i-1][j-1]이 x이고 word1[i]!=word2[j],word1이word2로 변하려면 교체를 한 번 증가해야 합니다. 횟수는 x+1입니다.
이외에 수조의 경계를 주의하십시오. dp[i][0]=i와 dp[0][j]=j 코드

#define MIN(a, b) ((a)
int minDistance(char * word1, char * word2){
    int** dp;
    int i, j, len1, len2;
    len1 = strlen(word1);
    len2 = strlen(word2);
    if (len1 == 0 || len2 == 0) {
        return len1 + len2;
    }
    dp = (int**)malloc(sizeof(int*) * (len1 + 1));
    for (i = 0; i < len1 + 1; i++) {
        dp[i] = (int*)malloc(sizeof(int) * (len2 + 1));
        dp[i][0] = i;
    }
    for (j = 1; j < len2 + 1; j++) {
        dp[0][j] = j;
    }
    for (i = 1; i < len1 + 1; i++) {
        for (j = 1; j < len2 + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = MIN(MIN(dp[i - 1][j - 1], dp[i][j - 1] + 1), dp[i - 1][j] + 1);
            } else {
                dp[i][j] = MIN(MIN(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1), dp[i - 1][j] + 1);
            }
        }
    }
    return dp[len1][len2];
}