w****x
发帖数: 2483 | 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上发现都简单了不少 |
t****a
发帖数: 1212 | |
c********r
发帖数: 286 | 3 DP学到了，多谢。头像问题确实应该解决，原来的+1
【在 t****a 的大作中提到】
: 哦也，果然还是原来的头像好看
|
w****x
发帖数: 2483 | 4
要赵雅芝的还是汤唯的，要不换个苍井空的吧
【在 c********r 的大作中提到】
: DP学到了，多谢。头像问题确实应该解决，原来的+1
|
c*****a
发帖数: 808 | |
w****x
发帖数: 2483 | 6
林青霞啊，看不出来？
【在 c*****a 的大作中提到】
: 这新头像是谁
|
c*****a
发帖数: 808 | 7 年轻版林青霞啊
印象中就东方不败
我昨天开始学dp...
计划:
LIS,Longest common sub-sequence, longest common substring, edit distance,
shortest distance in graph, chain matrix multiplication, subset sum, 0/1/
knapsack, travelling salesman
才做了前3题 |
c********r
发帖数: 286 | 8 汤唯+1
【在 w****x 的大作中提到】
:
: 林青霞啊，看不出来？
|
o***d
发帖数: 313 | 9 谢谢大牛,正在反复巩固dp中.
其实我一直觉得这个跟当年学的什么归纳法还是演绎法的数学方法极其相似.就是从f(n
-1)推出来f(n)的形式....
【在 w****x 的大作中提到】
: 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
: 得学到蛮多的，分享一下。
: 以前写过一个很挫的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;
|
b***m
发帖数: 5987 | |
|
|
w****x
发帖数: 2483 | 11
大牛谦虚了....
【在 b***m 的大作中提到】
: 不懂DP的掩面遁过……
|
b***m
发帖数: 5987 | 12 不是谦虚，是真不懂，要不我请二爷吃饭呢，就是为了请教DP啊。
【在 w****x 的大作中提到】
:
: 大牛谦虚了....
|
w****x
发帖数: 2483 | 13
嗯， 下次得和二爷吃饭的时候得讨教一下DFS
【在 b***m 的大作中提到】
: 不是谦虚，是真不懂，要不我请二爷吃饭呢，就是为了请教DP啊。
|
c********t
发帖数: 5706 | 14 先顶, 做一遍edit distance感觉一下。
把二维数组变为二维滚动数组，甚至降为用1维，我觉得很难。
【在 w****x 的大作中提到】
: 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
: 得学到蛮多的，分享一下。
: 以前写过一个很挫的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;
|
w***o
发帖数: 109 | 15 好贴，学习了。
【在 w****x 的大作中提到】
: 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
: 得学到蛮多的，分享一下。
: 以前写过一个很挫的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;
|
v*********t
发帖数: 7 | 16 我最近也在研究 DP的初始化
楼主能贴下你写的 Decode Ways的代码么
【在 w****x 的大作中提到】
: 发现这道题属于没见过肯定想不出来，知道怎么解也很难写对。昨天重新写了一下，觉
: 得学到蛮多的，分享一下。
: 以前写过一个很挫的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;
|
w****x
发帖数: 2483 | 17
//leetcode OJ --> get decode ways
int GetDecodeWays(const char* str)
{
assert(str);
int nLen = strlen(str);
if (nLen <= 0) return 0;
int a = 1;// 1 not 0
int b = (str[0] >= '1' && str[0] <= '9') ? 1 : 0;
for (int i = 1; i < nLen; i++)
{
int c = 0;
if ((str[i-1] == '1' && str[i] >= '0' && str[i] <= '9')
|| (str[i-1] == '2' && str[i] >= '0' && str[i] <= '6'))
c += a;
if (str[i] >= '1' && str[i] <= '9')
c += b;
a = b;
b = c;
}
return b;
}
【在 v*********t 的大作中提到】
: 我最近也在研究 DP的初始化
: 楼主能贴下你写的 Decode Ways的代码么
|
v*********t
发帖数: 7 | 18 int a = 1;// 1 not 0
int b = (str[0] >= '1' && str[0] <= '9') ? 1 : 0;
能分析下这两行初始化的思路吗
我是用test case测了才写对初始化的
【在 w****x 的大作中提到】
:
: //leetcode OJ --> get decode ways
: int GetDecodeWays(const char* str)
: {
: assert(str);
: int nLen = strlen(str);
: if (nLen <= 0) return 0;
: int a = 1;// 1 not 0
: int b = (str[0] >= '1' && str[0] <= '9') ? 1 : 0;
: for (int i = 1; i < nLen; i++)
|
