제목의 대의.

문자열 X 및 Y를 지정하여 세 가지 작업을 수행할 수 있습니다.
1, 문자 삭제
2, 문자 삽입
3. 문자 바꾸기
매 조작의 대가는 1이다. 상기 세 가지 조작을 운용하여 X를 Y로 바꾸는 데 필요한 최소 걸음수는 얼마인가?

문제풀이

dp[i][j]를 X의 앞 i자를 Y의 앞 j자로 변환하는 데 필요한 최소 단계
만약 X[i]==Y[j]라면 dp[i][j]=dp[i-1][j-1]
하면, 만약, 만약...Y[j]는 dp[i][j]=min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)

코드:

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAXN 1005

char x[MAXN],y[MAXN];

int dp[MAXN][MAXN];

int main()

{

    int n,m;

    while(~scanf("%d%s",&n,x+1))

    {

        memset(dp,0,sizeof(dp));

        scanf("%d%s",&m,y+1);

        dp[0][0]=0;

        for(int i=1; i<=n; i++)

            dp[i][0]=i;

        for(int j=1; j<=m; j++)

            dp[0][j]=j;

        for(int i=1; i<=n; i++)

            for(int j=1; j<=m; j++)

                if(x[i]==y[j])

                    dp[i][j]=dp[i-1][j-1];

                else

                {

                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;

                    dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);

                }

        printf("%d
",dp[n][m]);

    }

    return 0;

}

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

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

POJ3071: Football(확률 DP)

Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...

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

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

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다