편집 거리 대용량 입력에 대한 동적 프로그래밍

Question

잘 알려진 거리 편집 동적 프로그래밍 문제를 해결하고 있습니다. 문제는 두 개의 문자열 string1과 string2가 주어지며 문자 삭제, 삽입 및 대체 비용이 주어 지므로 작은 문자열 (크기 < = 10000)에 대해 내 코드가 작동하지만 더 큰 입력 (크기> = 100000)에 대해 컴파일러에서 "배열 크기 너무 큽니다 ". 동적 프로그래밍 (입력 크기 = 100000)을 사용하여 문제를 해결해야하는 경우이 오류를 어떻게 처리해야하는지 알려주세요. 여기 내 코드가 있습니다.

#include <iostream> 
#include <cstdio> 
#include <stdlib.h> 
#include <algorithm> 
#include <map> 
#include <queue> 
#include <iomanip> 
#include <string> 
#include <math.h> 
#include <limits> 
#include <map> 
#include <float.h> 
#include <limits.h> 
#include <string.h> 
using namespace std; 
#define rep(i,a,N) for(int i=a;i<N;++i) 
int DP[10000][10000],delete_cost,add_cost,replace_cost; 
string first,second; 
int Min(int x,int y,int z){ 
    int min=x<y?x:y; 
    min=min<z?min:z; 
    return min; 
} 

int Transform(int i,int j){ 
    if(DP[i][j]!=-1){ 
     //printf("DP is set\n"); 
     return DP[i][j]; 
    } 
    if(i==first.size()) 
     return (second.size()-j)*add_cost; 
    if(j==second.size()) 
     return (first.size()-i)*delete_cost; 
    if(first.at(i)!=second.at(j)){ 
     int add,del,rep; 
     add=Transform(i,j+1)+add_cost; 
     del=Transform(i+1,j)+delete_cost; 
     rep=Transform(i+1,j+1)+replace_cost; 
     return DP[i][j]=Min(add,del,rep); 
    } 
    else 
     return DP[i][j]=Transform(i+1,j+1); 

} 
    int main(){ 
    int T,a,b,k,ans; 
    scanf("%d",&T); 

    while(T--){ 
     memset(DP,-1,sizeof(DP)); 
     cin>>first; 
     cin>>second; 
     scanf("%d %d %d",&a,&b,&k); 
     add_cost=a; 
     delete_cost=b; 
     replace_cost=k; 
     //ans=Transform(0,0); 
     //if(ans<=k) 
      printf("%d\n",ans); 
     //else 
     // printf("%d\n",-1); 
    } 
return 0; 
} 

Answer 1

오른쪽, 32 비트 정수의 당신의 100000 * 100000 배열은 메모리 40 기가 바이트 차지하기 때문이다. 다른 알고리즘을 사용해야합니다. 특정 최대 값 인 k까지만 편집 거리를 계산해야하는 경우 O(n * (2k + 1)) 저장소 (여기서 n은 문자열 길이)를 사용하는 클래식 알고리즘의 수정 된 버전은 동적 프로그래밍의 중간 부분 인 2k + 1 만 사용하기 때문에 문자열 길이입니다. 매트릭스.