字符间的距离-动态规划

// 1.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> int minValue(int t1,int t2,int t3) { if(t1 < t2) { if(t1 < t3) return t1; else return t3; } else { if(t2 < t3) return t2; else return t3; } } int CalculateStringDistance(char* strA,int pABegin,int pAEnd,char* strB,int pBBegin,int pBEnd) { if(pABegin > pAEnd) { if(pBBegin > pBEnd) return 0; else return pBEnd - pBBegin+1; } if(pBBegin > pBEnd) { if(pABegin > pAEnd) return 0; else return pAEnd - pABegin+1; } if(strA[pABegin] == strB[pBBegin]) { return CalculateStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd); } else { int t1 = CalculateStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd); int t2 = CalculateStringDistance(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd); int t3 = CalculateStringDistance(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd); return minValue(t1,t2,t3)+1; } } //DP解法 int distance(char* strA,int lenA,char* strB,int lenB) { int *C = (int*)malloc(sizeof(int)*(lenA+1)*(lenB+1)); int i = 0,j = 0; for(i=0;i<=lenA;i++) // j = 0 C[i*(lenB+1)] = lenA; for(j=0;j<=lenB;j++) // i = 0 C[j] = lenB; for(i=1;i<=lenA;i++) { for(j=1;j<=lenB;j++) { //C[i][j] = min{C[i-1][j]+1,C[i][j-1]+1,C[i-1][j-1]+(A[i-1]==B[j-1])?0:1}; C[i*(lenB+1)+j] = minValue(C[(i-1)*(lenB+1)+j]+1,C[i*(lenB+1)+j-1]+1,C[(i-1)*(lenB+1)+j-1]+((strA[i-1] == strB[j-1])?0:1)); } } return C[lenA*(lenB+1)+lenB]; } int main() { char* A = "af"; char* B = "acdef"; int num = CalculateStringDistance(A,0,strlen(A)-1,B,0,strlen(B)-1); printf("两个字符串的距离:%d\n ",num); distance(A,strlen(A),B,strlen(B)); printf("两个字符串的距离:%d\n ",num); return 0; }

 

转载于:https://www.cnblogs.com/welsh-android-learning/p/3499368.html