資訊專欄INFORMATION COLUMN
摘要：源代碼管理中，指令，可以查找出編輯前后文件的差異，這是基于動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的。編輯距離，判斷字符串的相似程度，也是基于動(dòng)態(tài)規(guī)劃計(jì)算。
本文是《算法圖解》筆記應(yīng)用場(chǎng)景
一切脫離實(shí)際應(yīng)用場(chǎng)景的算法都是耍流氓！
生物學(xué)家根據(jù)最長(zhǎng)公共序列來確定 DNA 鏈的相似性，進(jìn)而判斷兩種動(dòng)物或疾病有多相似。最長(zhǎng)公共序列還被用來尋找多發(fā)性硬化癥治療方案。
源代碼管理中，git diff指令，可以查找出編輯前后文件的差異，這是基于動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的。
編輯距離（levenshtein distance），判斷字符串的相似程度，也是基于動(dòng)態(tài)規(guī)劃計(jì)算?？梢酝ㄟ^這個(gè)技術(shù)從拼寫檢查到判斷用戶上傳的資料是否是盜版。（這樣看來，我猜想大學(xué)論文查重應(yīng)該也是基于動(dòng)態(tài)規(guī)劃算法:P）
Microsoft Word等軟件中具有斷字功能，使用動(dòng)態(tài)規(guī)劃可以確定什么地方斷字以確保行長(zhǎng)一致。
最長(zhǎng)公共子串某個(gè)用戶在網(wǎng)站搜索框中輸入一個(gè)字符串 hish，但其實(shí)用戶想輸入的是 fish
介紹這個(gè)網(wǎng)站的可選字典里面只有 fish 和 vista 這兩個(gè)相似單詞
猜測(cè)用戶到底想要搜索的是什么字符串？
在動(dòng)態(tài)規(guī)劃中，目標(biāo)是要將某個(gè)指標(biāo)最大化，在這個(gè)例子中，要找出兩個(gè)單詞的公共子串。更大的那個(gè)即為結(jié)果。
| h | i | s | h | |
|---|---|---|---|---|
| f | 0 | 0 | 0 | 0 |
| i | 0 | 1 | 0 | 0 |
| s | 0 | 0 | 2 | 0 |
| h | 1 | 0 | 0 | 3 |
如果兩個(gè)字母不同，值為0
如果兩個(gè)字母相同，值為左上角鄰居的值加一
if word_a[i] == word_b[j]:
cell[i][j] = cell[i-1][j-1] + 1
else:
cell[i][j] = 0
最長(zhǎng)公共子序列
假設(shè)用戶不小心輸入了 fosh ，要判斷他原本要輸入的是 fish 還是 fort
這時(shí)候需要使用最長(zhǎng)公共子序列來比較
| f | o | s | h | |
|---|---|---|---|---|
| f | 1 | 1 | 1 | 1 |
| i | 1 | 1 | 1 | 1 |
| s | 1 | 1 | 2 | 2 |
| h | 1 | 1 | 2 | 3 |
如果兩個(gè)字母不同，就選擇上方和左方鄰居格子中較大的那個(gè)值
如果兩個(gè)字母相同，值為左上方格子中的值加一
if word_a[i] == word_b[j]:
cell[i][j] = cell[i-1][j-1] + 1
else:
cell[i][j] = max(cell[i-1][j], cell[i][j-1])
我的博客： http://vimiix.com
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/41397.html
摘要：題目給定兩個(gè)字符串求出它們的最長(zhǎng)公共字串說明比如在單詞和它們的最長(zhǎng)公共子序列是。最長(zhǎng)公共子串和最長(zhǎng)公共子序列的區(qū)別。 題目 給定兩個(gè)字符串,求出它們的最長(zhǎng)公共字串 var str1=abcdefg; var str2=xyzabcd; 說明：比如在單詞abcdefg和abcdefg它們的最長(zhǎng)公共子序列是abcd。尋找最長(zhǎng)子序列常用于遺傳學(xué)中，用于使用核苷酸堿基的首字母對(duì)DNA的描述（這...
摘要：若且，則是和的最長(zhǎng)公共子序列若且，則是和的最長(zhǎng)公共子序列。遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問題具有子問題重疊性質(zhì)。例如，在計(jì)算和的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出和及和的最長(zhǎng)公共子序列。 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 本章講解： 1. LCS（最長(zhǎng)公共子序列）O(n^2)的時(shí)間復(fù)雜...
摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關(guān)于字符串的文章的怎么翻譯匯集目錄非常希望強(qiáng)化博客的功能，比如分類，置頂。 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 最近在看算法和語言，基本屬于看知識(shí) --> java實(shí)現(xiàn) --> 整理blog 這個(gè)路線。 遇到問題查查st...
摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長(zhǎng)度不會(huì)超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個(gè)可能的最長(zhǎng)回文子序列為。數(shù)值為或者字符串不是一個(gè)合法的數(shù)值則返回。 說明 本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點(diǎn)：https://www.weiweiblog.c...
摘要：但不是和的最長(zhǎng)公共子序列，而序列和也均為和的最長(zhǎng)公共子序列，長(zhǎng)度為，而和不存在長(zhǎng)度大于等于的公共子序列。最長(zhǎng)公共子序列給定序列和，從它們的所有公共子序列中選出長(zhǎng)度最長(zhǎng)的那一個(gè)或幾個(gè)。為和的最長(zhǎng)公共子序列長(zhǎng)度。 最長(zhǎng)公共子序列（Longest Common Subsequence LCS）是從給定的兩個(gè)序列X和Y中取出盡可能多的一部分字符，按照它們?cè)谠蛄信帕械南群蟠涡蚺帕械玫?。LCS問...
閱讀 3299·2021-11-23 09:51
閱讀 951·2021-09-03 10:30
閱讀 3224·2021-08-31 09:40
閱讀 3284·2019-08-30 14:22
閱讀 909·2019-08-30 14:09
閱讀 2910·2019-08-30 13:21
閱讀 3245·2019-08-28 18:03
閱讀 2865·2019-08-26 13:44
