点击打开链接
思路: 线性动态规划
分析:
1 题目要求两个字符串的最小距离
2 假设dp[i][j]表示字符串1前i个字符和字符串2的前j个字符的最小距离,那么我们很容易知道。dp[0][0] = 0,因为两个空的字符串的距离为0
dp[0][j] = dp[0][j-1]+k , dp[i][0] = dp[i-1][0]+k
3 那么很明显考虑字符串1第i个字符和字符串2的第j个字符的时候,那么我们可以知道有三种情况,i字符和j字符匹配,i字符和空字符匹配,j字符和空字符匹配。那么就有dp[i][j] = min(dp[i-1][j-1]+abs(str1[i]-str2[j] , dp[i-1][j]+k , dp[i][j-1]+k ));
4 我们为了计算的方便把字符串从下标1读入,那么ans就是dp[len1][len2];
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 2010;
char str1[MAXN] , str2[MAXN];
int k , dp[MAXN][MAXN];
int solve(){
int len1 = strlen(str1+1);
int len2 = strlen(str2+1);
memset(dp , INF , sizeof(dp));
dp[0][0] = 0;
for(int i = 1 ; i <= len2 ; i++)
dp[0][i] = dp[0][i-1]+k;
for(int i = 1 ; i <= len1 ; i++)
dp[i][0] = dp[i-1][0]+k;
for(int i = 1 ; i <= len1 ; i++){
for(int j = 1 ; j <= len2 ; j++){
int tmp = dp[i-1][j-1]+abs(str1[i]-str2[j]);
tmp = min(tmp , dp[i-1][j]+k);
tmp = min(tmp , dp[i][j-1]+k);
dp[i][j] = min(dp[i][j] , tmp);
}
}
return dp[len1][len2];
}
int main(){
while(scanf("%s" , str1+1) != EOF){
scanf("%s" , str2+1);
scanf("%d" , &k);
printf("%d\n" , solve());
}
return 0;
}
分享到:
相关推荐
rqnoj的一些资料 c++的绝对对你有用。。。。。。
rqnoj ,题库。 密码锁(月赛) 动态规划,dp
很好的东西!省事省力省距离!免费啊免费啊
典型的排列组合题,几乎不需要什么解释。rqnoj第22题,程序写的很简练,初学者想想就懂了。
标程,有c++和Pascal版的。cena测试通过。RQNOJ测试通过。
Leetcode本项目使用的题库为 :star:主要使用Java书写算法,还有部分SQL语句练习,刚刚开始刷题,数量并不是很多 :grinning_face_with_sweat:我就不建翻译...TK题库 ATcoder 紫外线 RQNOJ YO玲珑学院 OJ彗星评测鸭 厨师