动态规划 leetcode 72题edit distance

一直分不清楚动态规划和贪心,今天好好啃一啃

贪心:Ai –> Ai+1

动归:A0,A1,A2….Ai –>Ai+1 判断问题的子结构,具有最优子结构时,动归适用

嘤 贪心的复杂度明显低于动归

在最长子序列中(不一定连续),贪心思路

最开始,缓冲区里为空;

看到了字符“1”,添加到缓冲区的最后,即缓冲区中是“1”;

看到了字符“4”,“4”比缓冲区的所有字符都大,因此将“4”添加到缓冲区的最后,得到“14”;

看到了字符“6”,“6”比缓冲区的所有字符都大,因此将“6”添加到缓冲区的最后,得到“146”;

看到了字符“2”,“2”比“1”大,比“4”小,因此将“4”直接替换成“2”,得到“126”;

看到了字符“8”,“8”比缓冲区的所有字符都大,因此将“8”添加到缓冲区的最后,得到“1268”;

看到了字符“9”,“9”比缓冲区的所有字符都大,因此将“9”添加到缓冲区的最后,得到“12689”;

看到了字符“7”,“7”比“6”大,比“8”小,因此将“8”直接替换成“7”,得到“12679”;

现在,缓冲区的字符数目为5,因此,数组A的LIS的长度就是5!

这样,时间复杂度变为每次都在一个递增的序列中替换或插入一个新的元素,所以为O(nlogn)。、

提问!但这种做法只能得到长度,并不能得到子序列本身

但是为什么是对的呢?在一个大佬的帮助下 理解了 大佬的解释是:相等的上升子序列,最后一个元素越小,越有利于之后使上升子序列的长度增加。 精辟! 而且反正替换的也是比这个数大的最小的数,如果下一个数比这个数大,也只会替换后面的数字 前面的也没什么影响

动归思路:从第一位开始到最后一位,依次计算所有递增序列的长度,保存,最后来做比较

总之就是要 降低问题的规模!!!

问题重述:Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

思路:

打表存储 和DNA测序一样的思路

贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution35 {
public:
int minDistance(string word1, string word2) {
int len1=word1.length();
int len2=word2.length();
int dis[len1+1][len2+1];
//初始化数据
for (int k = 0; k <len1+1 ; ++k) {
for (int i = 0; i <len2+1 ; ++i) {
dis[k][i]=INT;
}
}
for (int i = 0; i <len1+1 ; ++i) {
dis[i][0]=i;
}
for (int j = 0; j <len2+1 ; ++j) {
dis[0][j]=j;
}

//进行运算
for (int l = 1; l <len1+1 ; ++l) {
for (int i = 1; i <len2+1 ; ++i) {
if(word1[l-1]==word2[i-1]){
dis[l][i]=dis[l-1][i-1];
} else
dis[l][i]=min(dis[l-1][i-1],min(dis[l-1][i],dis[l][i-1]))+1;
}
}
return dis[len1][len2];
}

};