字符串的距离(动态规划) - leetcode 72
字符串的距离(动态规划) - leetcode 72
最近我发的N篇文章都会是动态规划相关的题目
，因为在刷leetcode的动态规划专题。动态规划虽然定义很简单，但是对于复杂的动态规划题目，很多时候还是很棘手的。
来看题
。
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
对于这道题，首先比较难很快的定义出一个状态，状态转换方程也比较绕。
从一个单词s1到单词s2，需要多少步操作能够达到呢？
比如从空字符串""到字符串"hello"，需要多少步呢？显然需要5步，因为一直加字符就好了。
那么从字符串"hello"到空字符串""，需要多少步呢？也只需要5步，因为一直减就好了。
我们定义状态dp(i,j)为：字符串s1(0,i)变成字符串s2(0,j)所需要的步数。
那么必有状态转移方程：
dp(i,j) = min(插入，删除，替换，相等)
假设s1(0,i) 是字符串str1c，s2(0,j)是字符串str2d
删除：dp(i, j) = dp(i-1, j) + 1 （删除c，则有str1与str2d）
插入：dp(i, j) = dp(i, j-1) + 1（在c后面添加d，str1cd与str2d，双方都去掉d，则有str1c与str2）
替换：dp(i, j) = dp(i-1, j-1) + 1
相等：dp(i, j) = dp(i-1, j-1)
状态转移方程不是简单的数学函数，而是一个组合函数，多个条件之间选择最小值。复杂的动态规划往往是这样。
最后整理一下写代码。
源代码：gcc
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define printf //printf
int min(int x, int y)
{
return x > y ? y : x;
}
/*
dp(i, j) 定义：字符串s1 0到i 与 字符串s2 0到j 之间的距离
也就是：s1(0, i) s2(0, j)之间的距离
*/
int minDistance(char* word1, char* word2) {
int l1 = strlen(word1);
int l2 = strlen(word2);
if (l1 == 0 && l2 == 0) {
return 0;
}
//初始化
int dp[l1+1][l2+1];
for(int i=0; i<=l1; ++i){
for(int j=0; j<=l2; ++j){
dp[i][j] = 0;
}
}
//一直删除，需要l1步
for(int i=0; i<= l1; ++i){
dp[i][0] = i;
printf("%d %d -> %d\n", i, 0, dp[i][0]);
}
//一直增加，需要l2步
for(int j=0; j<=l2; ++j){
dp[0][j] = j;
printf("%d %d -> %d\n", 0, j, dp[0][j]);
}
//自底向上
for(int i=1; i<= l1; ++i){
for(int j=1; j<= l2; ++j){
//置换
int replace = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1;
//插入： dp[i][j] = dp[i][j-1] + 1 因为s[0,j]与s[0,j-1]相隔一个字符
//删除： dp[i][j] = dp[i-1][j] + 1 因为s[0, i]与s[0, i-1]相隔一个字符
int ins_del = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);
dp[i][j] = min(replace, ins_del);
printf("%d %d -> %d\n", i, j, dp[i][j]);
}
}
return dp[l1][l2];
}
int main()
{
printf("%d\n", minDistance("ab", "a"));
return 0;
}