동적 계획 - 최적화 편집기 문제

문 제 는 Levenshtein 거 리 를 설명 하 는데 편집 거리 라 고도 부 릅 니 다. 두 문자열 사이 에 하나 에서 다른 문자열 로 전환 하 는 데 필요 한 최소 편집 작업 횟수 를 말 합 니 다.허 가 된 편집 작업 은 한 문 자 를 다른 문자 로 바 꾸 고 한 문 자 를 삽입 하여 한 문 자 를 삭제 하 는 것 을 포함한다.거 리 를 편집 하 는 알고리즘 은 먼저 러시아 과학자 Levenshtein 이 제기 한 것 이기 때문에 Levenshtein Distance 라 고도 부른다.Ex: 문자열 A: abcdefg 문자열 B: abcdef 는 문자 'g' 를 추가 하거나 삭제 하 는 방식 으로 목적 을 달성 합 니 다.이 두 가지 방안 은 모두 한 번 의 조작 이 필요 하 다.이 작업 에 필요 한 횟수 를 두 문자열 의 거리 로 정의 합 니 다.요구: 임의의 두 문자열 을 지정 하고 편집 거 리 를 계산 하 는 알고리즘 을 작성 합 니 다.

문제 풀이 사고 문제 추상: A 를 B 로 바 꾸 는 데 필요 한 최소 조작 걸음 수(B 가 A 로 변 하 는 최소 동작 걸음 수 일 수도 있 습 니 다. 두 각도 가 같 습 니 다. A 가 B 로 변 했 기 때 문 입 니 다. 삽 입 된 그림 이 있 으 면 B 가 A 로 변 하면 등가 가 삭 제 됩 니 다. A 가 B 로 변 하면 B 가 A 로 변 하면 등가 가 삽 입 됩 니 다. 걸음 수가 같 기 때 문 입 니 다. dp [x] [y] 를 사용 합 니 다.A 의 앞 x 자 를 B 의 앞 y 자로 바 꾸 는 데 필요 한 최소 동작 걸음 수 최 적 화 된 서브 구 조 를 나타 낸다. A 의 앞 x 자 를 B 의 앞 y 문자 로 바 꾸 는 데 필요 한 최소 동작 걸음 수 d [x] [y] 는 하위 문제 에 달 려 있다.

    1）A         ：
    if(A  x      B  y   )dp[x][y]=dp[x-1][y-1]+1 // A  x-1     B  y-1   ，            B       （  ）
    else dp[x][y]=dp[x-1][y-1] //  A         B       ， A  x     B  y       A  x-1     B  y-1   
    2）A          （   A     ）
    dp[x][y]=dp[x-1][y]+1  // A  x-1     B，           
    3）B          （   B     ）
    dp[x][y]=dp[x][y-1]+1  // B  y-1     A，           

    dp[x][y]=min{dp[x-1][y-1]+1 dp[x-1][y-1],dp[x-1][y]+1,dp[x][y-1]+1}

     x=0 ， A     ， A  B  Y         y，dp[0][y]=y;
      ，y=0 ，dp[x][0]=x;
               A  B       dp[a.length][b.length].
  **                         ，    i      i-1  **

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

알고리즘 서론 제10 장 기본 데이터 구조 실현 (스 택, 대기 열, 링크), 방과 후 문제 답

창고. 스 택 은 후진 선 출 전략 을 실현 하고 스 택 에 들 어가 거나 스 택 에 나 가 는 것 은 모두 스 택 꼭대기 지침 을 통 해 조작 합 니 다. 대열 대열 은 일종 의 선진 적 인 선발 전략 으로 줄 을...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

동적 계획 - 최적화 편집기 문제

좋은 웹페이지 즐겨찾기