For 40 years, computer scientists looked for a solution that doesn’t exist - The Boston Globe | 程式競賽 | kaif.io

程式競賽 /z/programming-contest

sayuan 積分 2

Wagner-Fischer algorithm1 長得跟 DP 版的 LCS2 實在很像，還以為也會跟 LCS 一樣有複雜度比較低的演算法

1

https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm#Calculating_distance

2

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS

回應 7 years ago

這是文章的子討論串，你可以回到上層查看所有討論和文章

回上層

Kmark 語法說明

Kmark 是一個類似 Markdown 語法的格式，以下為提供的功能:

種類	語法	呈現
斜體	兩邊加單星	兩邊加單星
粗體	兩邊加雙星	兩邊加雙星
刪除線	~~兩邊加雙曲號~~	~~兩邊加雙曲號~~
引用	> 左邊加個大於符號	左邊加個大於符號
列表	* 可用星號 * 也可以 - 減號 * 數字加點也可以	可用星號也可以 - 減號數字加點也可以
固定寬字	`abcdefghijk` 兩邊用倒引號包住	`abcdefghijk`
編碼區塊	``` function abc() ``` 上下都用三個倒引號包住	`function abc()`
連結	[這是連結][1] [1]: http://example.com 連結第一部份是文字，先用中括號包住，後面再加上 [編號]。第二部份是連結本身，放在文末，開頭是 [編號]: http	這是連結1 1 http://example.com

Kmark 語法說明

Kmark 是一個類似 Markdown 語法的格式，以下為提供的功能:

種類	語法	呈現
斜體	兩邊加單星	兩邊加單星
粗體	兩邊加雙星	兩邊加雙星
刪除線	~~兩邊加雙曲號~~	~~兩邊加雙曲號~~
引用	> 左邊加個大於符號	左邊加個大於符號
列表	* 可用星號 * 也可以 - 減號 * 數字加點也可以	可用星號也可以 - 減號數字加點也可以
固定寬字	`abcdefghijk` 兩邊用倒引號包住	`abcdefghijk`
編碼區塊	``` function abc() ``` 上下都用三個倒引號包住	`function abc()`
連結	[這是連結][1] [1]: http://example.com 連結第一部份是文字，先用中括號包住，後面再加上 [編號]。第二部份是連結本身，放在文末，開頭是 [編號]: http	這是連結1 1 http://example.com