做了一道edit distance,讨论DP的初始化阶段# JobHunting - 待字闺中
w*x
1 楼
发现这道题属于没见过肯定想不出来,知道怎么解也很难写对。昨天重新写了一下,觉
得学到蛮多的,分享一下。
以前写过一个很挫的DP版本:
int GetEditDist(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2];
bool bFound = false;
for (int i = 0; i < nLen2; i++)
{
if (str2[i] == str1[0])
bFound = true;
rec[i] = bFound ? i : i+1;
}
bFound = (str2[0] == str1[0]); //(str2[0] == str1[0]) not false
for (int i = 1; i < nLen1; i++)
{
if (str2[0] == str1[i])
bFound = true;
int nPrev = rec[0];
rec[0] = bFound ? i : i+1;
for (int j = 1; j < nLen2; j++)
{
int nMin = min(rec[j], rec[j-1]) + 1; //missing + 1
if (str1[i] == str2[j])
nMin = min(nPrev, nMin);
else nMin = min(nPrev+1, nMin);
nPrev = rec[j];
rec[j] = nMin;
}
}
int nRet = rec[nLen2-1];
delete []rec;
return nRet;
}
这个程序写的很烂,虽然考虑到了可以优化到一维数组但是初始状态写的巨复杂,而且
有一个bug就是当一个string为空的时候会崩溃。
一般觉得做DP题有3步:
1. 第一步肯定是想出递推规则
2. 第二步是选择DP数据结构然后优化,一般从递推公式可以选择二维数组 ==> 一维数
组 ==> 2,3个变量
3. 第三步是初始化DP的结构,比如如果是二维矩阵一般可以初始化第一行和第一列
4. 第四步是循环计算得到最后的结果
这题是两个string, 同样按这样步骤处理,但是初始化选择的是1而不是0(1是string第
一个字母,0是代表string为空的情况),如果初始化想到的不是空串(0)状态而是一个
字母的状态(空串作为单独逻辑提出来处理)很可能写成生面那种搓13的状态,而且很容
易出错。
==============================================================
后来换了一下初始状态为空串的写法,发现方便多了:
int GetEditDist2(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2+1];
for (int i = 0; i <= nLen2; i++)
rec[i] = i;
for (int i = 0; i < nLen1; i++)
{
int nPrev = rec[0];
rec[0] = i+1;
for (int j = 1; j <= nLen2; j++)
{
int nMin = min(rec[j-1], rec[j]) + 1;
int nAdd = str2[j-1] == str1[i] ? 0 : 1;
nMin = min(nMin, nPrev + nAdd);
nPrev = rec[j];
rec[j] = nMin;
}
}
int nRet = rec[nLen2];
delete []rec;
return nRet;
}
不过还是很无耻的出现了两个bug,
一个是
int nPrev = rec[0];
rec[0] = i+1;
这两行代码的顺序反了
另外一个是:
int nMin = min(rec[j-1], rec[j]) + 1;
这里忘+1了
其实把二维数组概念的DP映射到一维数组还是很麻烦的。
这里nPrev => f(i-1,j-1) rec[i-1] => f(i,j-1) rec[i] => f(i-1,j)
=============================================================
同样的想法用到coin change, longest common subsequence等DP上发现都简单了不少
得学到蛮多的,分享一下。
以前写过一个很挫的DP版本:
int GetEditDist(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2];
bool bFound = false;
for (int i = 0; i < nLen2; i++)
{
if (str2[i] == str1[0])
bFound = true;
rec[i] = bFound ? i : i+1;
}
bFound = (str2[0] == str1[0]); //(str2[0] == str1[0]) not false
for (int i = 1; i < nLen1; i++)
{
if (str2[0] == str1[i])
bFound = true;
int nPrev = rec[0];
rec[0] = bFound ? i : i+1;
for (int j = 1; j < nLen2; j++)
{
int nMin = min(rec[j], rec[j-1]) + 1; //missing + 1
if (str1[i] == str2[j])
nMin = min(nPrev, nMin);
else nMin = min(nPrev+1, nMin);
nPrev = rec[j];
rec[j] = nMin;
}
}
int nRet = rec[nLen2-1];
delete []rec;
return nRet;
}
这个程序写的很烂,虽然考虑到了可以优化到一维数组但是初始状态写的巨复杂,而且
有一个bug就是当一个string为空的时候会崩溃。
一般觉得做DP题有3步:
1. 第一步肯定是想出递推规则
2. 第二步是选择DP数据结构然后优化,一般从递推公式可以选择二维数组 ==> 一维数
组 ==> 2,3个变量
3. 第三步是初始化DP的结构,比如如果是二维矩阵一般可以初始化第一行和第一列
4. 第四步是循环计算得到最后的结果
这题是两个string, 同样按这样步骤处理,但是初始化选择的是1而不是0(1是string第
一个字母,0是代表string为空的情况),如果初始化想到的不是空串(0)状态而是一个
字母的状态(空串作为单独逻辑提出来处理)很可能写成生面那种搓13的状态,而且很容
易出错。
==============================================================
后来换了一下初始状态为空串的写法,发现方便多了:
int GetEditDist2(const char* str1, const char* str2)
{
assert(str1 && str2);
int nLen1 = strlen(str1);
int nLen2 = strlen(str2);
int* rec = new int[nLen2+1];
for (int i = 0; i <= nLen2; i++)
rec[i] = i;
for (int i = 0; i < nLen1; i++)
{
int nPrev = rec[0];
rec[0] = i+1;
for (int j = 1; j <= nLen2; j++)
{
int nMin = min(rec[j-1], rec[j]) + 1;
int nAdd = str2[j-1] == str1[i] ? 0 : 1;
nMin = min(nMin, nPrev + nAdd);
nPrev = rec[j];
rec[j] = nMin;
}
}
int nRet = rec[nLen2];
delete []rec;
return nRet;
}
不过还是很无耻的出现了两个bug,
一个是
int nPrev = rec[0];
rec[0] = i+1;
这两行代码的顺序反了
另外一个是:
int nMin = min(rec[j-1], rec[j]) + 1;
这里忘+1了
其实把二维数组概念的DP映射到一维数组还是很麻烦的。
这里nPrev => f(i-1,j-1) rec[i-1] => f(i,j-1) rec[i] => f(i-1,j)
=============================================================
同样的想法用到coin change, longest common subsequence等DP上发现都简单了不少