问答

当前位置
  • 首页
  • 问答
  • K Edit Distance超级难理解。求解释。

K Edit Distance超级难理解。求解释。

  • Ta: 马克助教

我了解大概思路,但对这道题DP细节还是不完全清楚。

看到答案,关键代码是DP的这里:

                                  if (target.charAt(j - 1) - 'a' == i) {
                    next[j] = Math.min(dp[j - 1], Math.min(next[j - 1] + 1, dp[j] + 1));
                } else {
                    next[j] = Math.min(dp[j - 1] + 1, Math.min(next[j - 1] + 1, dp[j] + 1));
                }

能不能解释一下next[j],dp[j - 1],next[j - 1],dp[j] + 1分别是什么?
为什么两种情况都要共享 Math.min(next[j - 1] + 1, dp[j] + 1) ?
能解释下这个dp的关键部分不?
谢谢。

3 个回复

2017-07-06 马同学

理解这个问题首先要理解 edit distance的状态转移方程。
这题本质是在Trie树上做动态规划,类似于每一个节点上,表示从root走到这个节点形成的前缀与字符串的每一个前缀的编辑距离,这是基本思路。

dp[i]是当前结点对应的单词到target第i位第最小花费
next与dp一个含义,相当于dp'接下来的查找如果还用dp,那么会对上一层有影响,所以需要另一个数组。


2017-07-07 Y同学

大概思路了解了。

可是请问这个dynamic programming部分?:
next[j] = Math.min(dp[j - 1] + 1, Math.min(next[j - 1] + 1, dp[j] + 1));

为什么这里dp和next数组会混着用?这句话到底什么意思? 尤其是这个部分: Math.min(next[j - 1] + 1, dp[j] + 1).

谢谢。


2017-07-20 W同学

尝试讲讲我的理解。
a. 首先是dpnext
我们都知道在最一般的edit distance问题里面,dp[i][j] 代表着 word1[0:i]word2[0:j]的编辑距离,并且很容易知道这样的转移方程:
if (word1.charAt(i - 1) == word2.char(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // 字符相同,不需要编辑
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1]
, Math.min(dp[i][j - 1], dp[i - 1][j]));
// 字符不一,那么存在insertion或subsitution,
// 意味着编辑距离为之前最小可能的编辑距离+1
}
捋清了这个,再来理解dpnext就很容易:
我们注意到上面的转移方程任意时候都只需要至多前一步的信息,所以我们只需要两个数组,一个标记前一步的情形,一个标记现在的情形 i.e. 用dp[j] 标记 以前的dp[i - 1][j], 以next[j] 代表以前的dp[i][j]。 那么也必然有:
if (word1.charAt(i - 1) == word2.char(j - 1)) {
next[j] = dp[j - 1]; // 老的dp[i][j] => next[j],
//老的dp[i - 1][j - 1] => dp[j - 1]
} else {
next[j]= 1 + Math.min(dp[j - 1],
Math.min(next[j - 1], dp[j]));
// 老的dp[i][j-1] => next[j - 1],
//老的dp[i - 1][j] => dp[j]
}

b. 其次是具体到本题标答的转移方程问题。
我也不太理解在九章给出的答案里为什么字符相同时是next[j] = min(dp[j-1], next(j-1)+1, dp[j]+1), 我的体会是用next[j] = dp[j - 1]就足够了,也可以通过OJ。事实上,next[j] = dp[j - 1]意味着不进行任何编辑,那么必然是要比next(j-1)+1dp[j]+1都要小的

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1