[理工] 105中央演算法
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1547285366.A.967.html
推
01/12 18:18,
7年前
, 1F
01/12 18:18, 1F
→
01/12 18:19,
7年前
, 2F
01/12 18:19, 2F
推
01/12 18:30,
7年前
, 3F
01/12 18:30, 3F
我懂了，你寫的比較好理解，感謝
※ 編輯: bmpss92196 (114.36.79.95), 01/12/2019 19:06:47