作者bmpss92196 (bmpss92196)
看板Grad-ProbAsk
标题[理工] 105中央演算法
时间Sat Jan 12 17:29:23 2019
https://imgur.com/a/vc9bQQU
想请问林立宇老师答案的问题，有点不懂
(a) c[i,j] = min{ c[i-1,j]+cost(delete)
{ c[i,j-1]+cost(insert)
{ c[i-1,j-1]+cost(substitution) if ai!=bj
{ c[i-1,j-1] if ai=bj
因为要把A=a1...ai调整成B=b1...bj，所以若用delete砍掉ai
剩下递回去求a1...ai-1 调整成b1...bj
同理若用insert增加ai+1，剩下再用递回去求a1...ai+1调整成b1...bj-1？
不太理解为何insert不是c[i+1,j]
a1...ai+1 调整成 b1...bj
另外b小题我理解是对的吗？
(b) c[i,0] = i*cost(delete) B没字元，a1~ai要全部砍掉才会变B
c[0,j] = j*cost(insert) A没字元，只能一个一个增加到B
谢谢!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.36.79.95
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547285366.A.967.html
2F：→ y2j60537: 我的理解是这样 不知道这样表达能不能理解 01/12 18:19
3F：推 y2j60537: 然後boundary condition我也是这样理解的 01/12 18:30
我懂了，你写的比较好理解，感谢
※ 编辑: bmpss92196 (114.36.79.95), 01/12/2019 19:06:47