1樓：陳肖
今天剛好刷到這道題，總共兩種變種，可以用DP完成。
Edit Distance
Delete Operation for Two Strings
2樓：Coldwings
DP/最短路均可解。如果不知道怎麼寫O(N^2)的DP優化，很簡單啊，把問題轉成最短路上SPFA即可。
以數對(I, J)視為節點，表達A串到第I位前的部分與B串J位前部分匹配所需的最小修改距離。顯然NM個點，2NM條邊的圖。根據SPFA的迭代情況，也就近似平方級了。
3樓：Mr.Rabbit
F(n, m): min cost to make A[0, n] to B[0, m].
if A[n] == B[m], F(n, m) = Math.min(F(n-1, m-1), Q(n, m));
Q(n, m) is the condition where we want to add/delete to the end of A. two branches,
1. Delete: Min(F(0, m),...,F(n-1, m))+2;
2. Insert: Min(F(n,0)+m,...,F(n, m-1)+1)+2;
if A[n] != B[m], F(n, m) = Q(n,m).
For base condition like F(0, m) or F(n, 0), u should know that.....
一道IT筆試題？
貓咪 1 9是揹包問題 f x min f x k i 1 f x k i min f x 1,f x k i 超過10時f x min f x 10 1,f x 9 3 而fabs f x f x 1 1，所以這裡應該是貪心。int f x 此為亂答 既然是按鍵，按太多肯定不爽。把1 10000溫...
一道阿里筆試題，思路應該是怎樣？
納尼思密達 import com.alibaba.fastjson.JSONObject public class Test int k 1,i arr.length k j 0 int tmp arr i while j arr.length j handle arr,i,j,i,tmp i ar...
一道演算法筆試題，各位大神幫幫看 怎麼算好？
一,在剩餘r個裡面抽取s個,使用s r選取下乙個.可以證明每個選擇的概率都是s r.1.第n 1個選擇概率是s r.2.當n 1時，當前樣本選擇的概率為前乙個選中的概率乘以選中當前的概率s r s 1 r 1 加上前乙個沒選中乘以選中當前的概率 1 s r s r 1 二者相加之和為s r.故每個樣...