算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃(編輯距離)(留存版)
【正文】 or(j=1。i=n。i=n。i++) //從i變到0字符串，i個(gè)需要i次(添加) d[i][0]=i。四、代碼及解釋（注釋）includeincludefstreamincludeincludeusing namespace std。要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。 輸入文件示例輸出文件示例fxpimu5xwrs二、分析 對(duì)于本問題，大體思路為：把求解編輯距離分為字符串A從0個(gè)字符逐漸增加到全部字符分別想要變?yōu)樽址瓸該如何變化以及變化的最短距離。 FILE *fp。j=m。i++) { for(j=1。}/*輸入：fxpimu xwrs輸出：5*/五、復(fù)雜度分析以下為核心代碼部分：for(i=0。i=n?？偨Y(jié)：綜上兩點(diǎn)，可知本題采用了動(dòng)態(tài)規(guī)劃的思想來解決，并能得到正確的答案。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃 矩陣 字符串操作數(shù) 編輯距離 一、問題描述基本概念：設(shè)A和B是2個(gè)字符串。具體來說，首先選用數(shù)組a1存儲(chǔ)字符串A(設(shè)長(zhǎng)度為n)，a2存儲(chǔ)字符串B(設(shè)長(zhǎng)度為m)，d矩陣來進(jìn)行具體的運(yùn)算；這里有兩個(gè)特殊情況比較簡(jiǎn)單可以單獨(dú)考慮，即A的長(zhǎng)度為0
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1