算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃(編輯距離)(編輯修改稿)
2024-09-01 16:48 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 證明理論前提：動(dòng)態(tài)規(guī)劃的基本思想與分治法類似，也是將待求解的問(wèn)題分解成若干份的子問(wèn)題，先分別解決好子問(wèn)題，然后從子問(wèn)題中得到最終解。但動(dòng)態(tài)規(guī)劃中的子問(wèn)題往往不是相互獨(dú)立的，而是彼此之間有影響。該算法的有效性依賴于兩個(gè)重要的性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和問(wèn)題重疊性質(zhì)。最有子結(jié)構(gòu)性：以自底向上的方法遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。重疊子問(wèn)題性：每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，利用動(dòng)態(tài)規(guī)劃對(duì)每一個(gè)子問(wèn)題只解一次，并將其存入表格中，下次用到該子問(wèn)題的解時(shí)，只要查找表格即可。本題：本題首先符合最優(yōu)子結(jié)構(gòu)性，即讓字符串A從1開(kāi)始遞增到最終長(zhǎng)度n，也就是從只有一個(gè)字符開(kāi)始計(jì)算，每增加一個(gè)字符計(jì)算一次，符合自底向上的方法遞歸地解決子問(wèn)題；其次符合重疊子問(wèn)題性，每增加一個(gè)字符計(jì)算的時(shí)候總要用到前一狀態(tài)時(shí)的編輯距離，并且本題我采用了矩陣來(lái)存儲(chǔ)舊子問(wèn)題的數(shù)據(jù)，都只計(jì)算了一次，所以也符合?？偨Y(jié)：綜上兩點(diǎn)，可知本題采用了動(dòng)態(tài)規(guī)劃的思想來(lái)解決，并能得到正確的答案。四、代碼及解釋（注釋）includeincludefstreamincludeincludeusing namespace std。const int MAX=1000。int min(int a,int b){ if(a=b) return b。 else
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1