프로 그래 밍 의 아름다움: 두 문자열 의 싱크로 율 계산 - 동적 계획 실현

문제 설명: 두 문자열 을 같은 기본 동작 으로 정의 합 니 다. 다음 과 같 습 니 다. 1.     문자 수정 되다 b） 2.     문자 추가 ... 와 같다 abed 되다 abedd) 3.     문자 삭제 jackbllog 되다 잭 블 로그 jackblog 에서 jackblog 로 하나만 삭제 하거나 하나만 추가 하면 됩 니 다. l 두 문자열 을 똑 같이 바 꿀 수 있 습 니 다.이 작업 에 필요 한 횟수 를 두 문자열 의 거리 로 정의 합 니 다. L, 싱크로 율 을 1 / (L + 1) 로 정의 합 니 다. 거리 플러스 1 의 역수 다.그럼 잭 블 로그 와 잭 블 로그 의 싱크로 율 은? 1/1+1=1/2=0.5 즉, 두 문자열 의 싱크로 율 은? 0.5。 두 문자열 을 지정 하 십시오. 아 는 사람 을 계산 할 지 여 부 를 쓰 시 겠 습 니까?분석 문제: 본 문 제 는 다단 계 단계 의 결정 문제 로 모든 단계 의 최 적 화 된 선택 은 앞에서 가장 좋 은 선택의 영향 을 받 을 수 있다. 우 리 는 동태 계획 을 이용 하여 실현 할 수 있다. 1. 하나의 문 제 를 정의 하고 2. 서브 문 제 를 가장 잘 푸 는 중첩 방식 을 확정 할 수 있다.이 문 제 를 예 로 들 어 source 문자열 에 n 개의 문자 가 있다 고 가정 합 니 다. target 문자열 에 m 개의 문자 가 있다 고 가정 합 니 다. 문 제 를 source 의 1 - n 문 자 를 target 의 1 - m 문자 로 변환 하 는 데 필요 한 최소 편집 횟수 (최소 편집 거리) 로 정의 하면그 하위 문 제 는 source 의 1 - i 문 자 를 target 의 1 - j 문자 로 바 꾸 는 데 필요 한 최소 편집 횟수 로 정의 할 수 있 습 니 다. 이것 이 바로 이 문제 의 가장 좋 은 하위 구조 입 니 다.우 리 는 d [i, j] 로 source [1. i] 에서 target [1. j] 사이 의 최소 편집 거 리 를 표시 하면 d [i, j] 의 전달 관 계 를 이렇게 계산 할 수 있다.  source [i] 가 target [j] 와 같다 면:  d[i, j] = d[i-1, j-1] + 0                                               (푸 시 1)  source [i] 가 target [j] 와 같 지 않 으 면 삽입, 삭제, 교체 세 가지 전략 에 따라 세 가지 전략 으로 얻 은 편집 거 리 를 계산 한 다음 에 가장 작은 하 나 를 가 져 옵 니 다.  d[i, j] = min(d[i, j - 1] + 1，d[i - 1, j] + 1，d[i - 1, j - 1] + 1 )            (푸 시 2)  d [i, j - 1] + 1 은 source [i] 에 대한 삽입 작업 을 수행 한 후 최소 편집 거 리 를 계산 하 는 것 을 나타 낸다. d [i - 1, j] + 1 은 source [i] 에 대한 삭제 작업 을 수행 한 후 최소 편집 거 리 를 계산한다. d [i - 1, j - 1] + 1 은 source [i] 를 target [i] 로 교체 한 후 최소 편집 거 리 를 계산한다.  d [i, j] 의 경계 값 은 target 이 빈 문자열 (m = 0) 이나 source 가 빈 문자열 (n = 0) 일 때 계 산 된 편집 거리 입 니 다.  m = 0, 모든 i: d [i, 0] = i n = 0, 모든 j: d [0, j] = j          앞에서 분석 한 최 적 화 된 서브 구조, 최 적 화 된 전달 관계 와 경계 값 에 따라 동적 계획 법 으로 최소 편집 거 리 를 계산 하 는 알고리즘 을 쓰 는 것 이 쉬 워 집 니 다. 다음 코드 는 두 문자열 의 최소 편집 거 리 를 계산 하 는 알고리즘 입 니 다.

public class StringSimilar {
	public int fun(String source,String target){
		int i,j;
		int[][] d = new int[source.length()+1][target.length()+1];
		for(i=1;i<source.length()+1;i++){/*      */
			d[i][0]=i;
		}
		for(j=1;j<target.length()+1;j++){/*      */
			d[0][j]=j;
		}
		for(i=1;i<source.length()+1;i++){/*      */
			for(j=1;j<target.length()+1;j++){
				if(source.substring(i-1, i).equals(target.substring(j-1, j))){
					d[i][j]=d[i-1][j-1];/*source  i  target  j    */
				}else{/*                */
					d[i][j]=min(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1]+1);
				}
			}
		}
		return d[source.length()][target.length()];
	}
	private int min(int i, int j, int k) {
		int min = i<j?i:j;
		min = min<k?min:k;
		return min;
	}
	public static void main(String[] args) {
		StringSimilar ss = new StringSimilar();
		System.out.println(ss.fun("SNOWY", "SUNNY"));//3
		System.out.println(ss.fun("a", "b"));//1
		System.out.println(ss.fun("abdd", "aebdd"));//1
		System.out.println(ss.fun("travelling", "traveling"));//1
	}
}

요약:
주해: [1] 최 우선 서브 구조: 다단 계 결정 문제 에 대해 각 단계 의 최 우선 결정 서열 의 서브 서열 도 최 우선 이 고 결정 서열 이 '무 후 효성' 을 가지 면 이 결정 방법 을 최 우선 서브 구조 로 이해 할 수 있다.  【 2 】 무 후 효성: 동태 기획 법의 최 우선 해 는 보통 일련의 최 우선 결정 으로 구 성 된 결정 서열 이다. 최 우선 서브 구 조 는 바로 이런 최 우선 결정 서열 중의 하위 서열 이다. 각 하위 서열 에 대해 최 우선 결정 을 하면 새로운 최 우선 결정 (하위) 서열 이 생 길 수 있다. 만약 에 특정한 결정 이 현재 최 우선 결정 하위 서열 의 영향 만 받는다 면현재 의 결정 이 발생 할 수 있 는 새로운 최 우선 결정 서브 시퀀스 의 영향 을 받 지 않 으 면 이 최 우선 결정 이 후 효성 이 없 음 을 이해 할 수 있다.