동적 계획 알고리즘 - 문자열 변환 최소 대가 문제

제목 설명
두 문자열 str1 과 str2 를 지정 하고 세 개의 정수 ic, dc, rc 를 지정 합 니 다. 각각 한 문 자 를 삽입, 삭제, 교체 하 는 대 가 를 의미 하 며 str1 을 str2 로 편집 하 는 최소 대 가 를 되 돌려 줍 니 다.예: str1 = "abc"  str2="adc"  ic=5    dc=3   rc = 2, "abc" 편집 에서 "adc" 로 b 를 d 로 교체 하 는 대가 가 가장 적 고 2 입 니 다.str1="abc"   str2="adc"  ic=5    dc=3   rc = 10, "abc" 에서 "adc" 로 편집 하고 b 를 먼저 삭제 한 다음 d 를 삽입 하 는 대가 가 가장 적 습 니 다. 8 입 니 다.
분석 하 다.
str 1 길이 가 M [0..............................................................................
dp [i] [j] 는 str1 [0... i - 1] 을 str2 [0... j - 1] 로 편집 한 최소 편집 대 가 를 나타 낸다. dp 크기 는 (M + 1) * (N + 1) 로 빈 문자열 부터 계산 하기 위 한 것 이다. 즉, dp [0] [0] 은 빈 문자열 에서 빈 문자열 로 편집 하 는 최소 편집 대 가 를 나타 낸다.dp [] [] 생 성 방법:

dp [0] [0] 은 빈 문자열 이 빈 문자열 로 편집 되 었 음 을 나타 내 므 로 dp [0] [0] = 0;

첫 번 째 줄 dp [0] [j] 를 구하 고 빈 문자열 을 str2 [0............................................................

첫 번 째 열 dp [i] [0], str1 [0... i - 1] 을 빈 문자열 로 편집 하면 dp [i] [0] = dc * i;

dp [i] [j], 즉 str1 [0... i - 1] 을 str2 [0.......................................................

str1 [0......................................................................증가

str1 [0.......................................................................삭제

str1 [i - 1] = str2 [j - 1], dp [i] [j] = dp [i - 1] [j - 1];아무것도 안 해도 돼 (cost = 0)

str1 [i - 1]! =str2 [j - 1], dp [i] [j] = dp [i - 1] [j - 1] + rc;고 쳐

한 마디 로 하면 dp [i] [j] 는 틀림없이 어떤 조작 을 증가, 삭제, 수정 한 후에 아무것도 하지 않 아 도 된다 (cost = 0).

import org.apache.commons.lang3.RandomStringUtils;
import org.junit.Test;

/**
 * Author: zxh
 * Date: 2019/2/21 16:49
 * Email: 
 * Desc:
 */
public class TestDynamicPlanTransferStringLeastCost {

    private static final int aLen = 5;
    private static final int bLen = 5;
    private static final int insertCost = 5;
    private static final int deleteCost = 6;
    private static final int replaceCost = 7;


    @Test
    public void test() {
        String source = RandomStringUtils.random(aLen, false, true);
        String target = RandomStringUtils.random(bLen, false, true);

//        String source = "123";
//        String target = "124";

        System.out.println("source   ：" + source);
        System.out.println("target   ：" + target);
        //dp[i][j]  a i （0 ，1 ...  index ）  ，   b j （0 ，1 ...  index ）       
        int[][] dp = new int[aLen + 1][bLen + 1];

        //          ,  index=0    
        for (int j = 0; j <= bLen; j++) {
            dp[0][j] = j * insertCost;
        }
        //          ,  index=0    
        for (int i = 0; i < aLen + 1; i++) {
            dp[i][0] = i * deleteCost;
        }

        for (int i = 0; i < aLen; i++) {
            for (int j = 0; j < bLen; j++) {
                char charA = source.charAt(i);
                char charB = target.charAt(j);
                if (charA == charB) {
                    dp[i + 1][j + 1] = dp[i][j];
                } else {
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i + 1][j] + insertCost, dp[i][j + 1] + deleteCost), dp[i][j] + replaceCost);
                }
            }
        }

        System.out.println("    dp：");
        for (int i = 0; i <= aLen; i++) {
            for (int j = 0; j <= bLen; j++) {
                System.out.print(dp[i][j] + ",");
            }
            System.out.println();
        }
    }
}

결과 예시

source   ：02118
target   ：89406
    dp：
0,5,10,15,20,25,
6,7,12,17,15,20,
12,13,14,19,21,22,
18,19,20,21,26,28,
24,25,26,27,28,33,
30,24,29,33,34,35,

Process finished with exit code 0