亚洲国产日韩一级,欧美一区二区日韩,国产精品成人一区

程序員編程藝術(shù)-----第二十八 ~ 二十九章-----最大連續(xù)乘積子串、字符串編輯距離

Posted on 2013-05-28 22:18 鑫龍閱讀(347) 評(píng)論(0) 編輯收藏引用所屬分類: JULY_程序員編程藝術(shù)

第二十八~二十九章：最大連續(xù)乘積子串、字符串編輯距離

前言

時(shí)間轉(zhuǎn)瞬即逝，一轉(zhuǎn)眼，又有4個(gè)多月沒來更新blog了，過去4個(gè)月都在干啥呢？對(duì)的，今2013年元旦和朋友利用業(yè)余時(shí)間一起搭了個(gè)方便朋友們找工作的編程面試算法論壇：為學(xué)論壇http://www.51weixue.com/。最近則開始負(fù)責(zé)一款在線編程挑戰(zhàn)平臺(tái)：英雄會(huì)http://hero.pongo.cn/，包括其產(chǎn)品運(yùn)營，出題審題，寫代碼測試，制定比賽規(guī)則等等。

前幾天跟百度的幾個(gè)朋友線下閑聊，聽他們說，百度校招群內(nèi)的不少朋友在找工作的時(shí)候都看過我的blog，一聽當(dāng)即便激起了自己重寫此blog的欲望，恰巧眼下陽春三月(雖說已是3月，奇妙的是，前兩天北京還下了一場大雪)，又是找工作的季節(jié)(相對(duì)于每年的9月份來說，3月則是一個(gè)小高潮)，那就從繼續(xù)更新專為IT人員找工作時(shí)準(zhǔn)備筆試面試的程序員編程藝術(shù)系列開始吧。

再者從去年4月份上傳的編程藝術(shù)前27章的PDF文檔的1.3萬下載量來看http://download.csdn.net/detail/v_july_v/4256339，此系列確確實(shí)實(shí)幫助了成千上萬的人。Yeah，本文講兩個(gè)問題，

第二十八章、最大連續(xù)乘積子串，
第二十九章、字符串編輯距離，

這兩個(gè)問題皆是各大IT公司最喜歡出的筆試面試題，比如說前者是小米2013年校招筆試原題，而后者則更是反復(fù)出現(xiàn)，如去年9月26日百度一二面試題，10月9日騰訊面試題第1小題，10月13日百度2013校招北京站筆試題第二大道題第3小題，及去年10月15日2013年Google校招筆試最后一道大題皆是考察的這個(gè)字符串編輯距離問題。

OK，歡迎朋友們在本文下參與討論，如果在線編譯自己的代碼（編程語言任選C/C++/Java/C#），可以上英雄會(huì)提交你的代碼，有任何問題，歡迎隨時(shí)不吝批評(píng)或指正，感謝。

第二十八章、最大連續(xù)乘積子串

題目描述：給一個(gè)浮點(diǎn)數(shù)序列，取最大乘積連續(xù)子串的值，例如 -2.5，4，0，3，0.5，8，-1，則取出的最大乘積連續(xù)子串為3，0.5，8。也就是說，上述數(shù)組中，3 0.5 8這3個(gè)數(shù)的乘積3*0.5*8=12是最大的，而且是連續(xù)的。

提醒：此最大乘積連續(xù)子串與最大乘積子序列不同，請勿混淆，前者子串要求連續(xù)，后者子序列不要求連續(xù)。也就是說：最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence，LCS）的區(qū)別：

子串（Substring）是串的一個(gè)連續(xù)的部分，
子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；

更簡略地說，前者（子串）的字符的位置必須連續(xù)，后者（子序列LCS）則不必。比如字符串“ acdfg ”同“ akdfc ”的最長公共子串為“ df ”，而它們的最長公共子序列LCS是“ adf ”，LCS可以使用動(dòng)態(tài)規(guī)劃法解決。

解答：

解法一、窮舉，所有的計(jì)算組合：
或許，讀者初看此題，自然會(huì)想到最大乘積子序列問題類似于最大子數(shù)組和問題：http://blog.csdn.net/v_JULY_v/article/details/6444021，可能立馬會(huì)想到用最簡單粗暴的方式：兩個(gè)for循環(huán)直接輪詢。

double max=0;
double start=0;
double end=0;
for (int i=0;i<num;i++) {
double x=arrs[i];
for (int j = i+1; j < num; j++) {
x*=arrs[j];
if(x>max){
max=x;
start=arrs[i];
end=arrs[j];
}
}

解法二、雖說類似于最大子數(shù)組和問題，但實(shí)際上具體處理起來諸多不同。為什么呢，因?yàn)槌朔e子序列中有正有負(fù)也還可能有0。我們可以把問題簡化成這樣：數(shù)組中找一個(gè)子序列，使得它的乘積最大；同時(shí)找一個(gè)子序列，使得它的乘積最小（負(fù)數(shù)的情況）。因?yàn)殡m然我們只要一個(gè)最大積，但由于負(fù)數(shù)的存在，我們同時(shí)找這兩個(gè)乘積做起來反而方便。也就是說，不但記錄最大乘積，也要記錄最小乘積。So，我們讓

maxCurrent表示當(dāng)前最大乘積的candidate，
minCurrent反之，表示當(dāng)前最小乘積的candidate，
而maxProduct則記錄到目前為止所有最大乘積candidates的最大值。

（以上用candidate這個(gè)詞是因?yàn)橹皇强赡艹蔀樾乱惠喌淖畲?最小乘積）

由于空集的乘積定義為1，在搜索數(shù)組前，maxCurrent，minCurrent，maxProduct都賦為1。
假設(shè)在任何時(shí)刻你已經(jīng)有了maxCurrent和minCurrent這兩個(gè)最大/最小乘積的candidates，新讀入數(shù)組的元素x(i)后，新的最大乘積candidate只可能是maxCurrent或者minCurrent與x(i)的乘積中的較大者，如果x(i)<0導(dǎo)致maxCurrent<minCurrent，需要交換這兩個(gè)candidates的值。
當(dāng)任何時(shí)候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent為1，類似的可以更新minCurrent。任何時(shí)候maxCurrent如果比最好的maxProduct大，更新maxProduct。
代碼一：

template <typename Comparable>
Comparable maxprod( const vector<Comparable>&v)
{
int i;
Comparable maxProduct = 1;
Comparable minProduct = 1;
Comparable maxCurrent = 1;
Comparable minCurrent = 1;
//Comparable t;
for( i=0; i< v.size() ;i++)
{
maxCurrent *= v[i];
minCurrent *= v[i];
if(maxCurrent > maxProduct)
maxProduct = maxCurrent;
if(minCurrent > maxProduct)
maxProduct = minCurrent;
if(maxCurrent < minProduct)
minProduct = maxCurrent;
if(minCurrent < minProduct)
minProduct = minCurrent;
if(minCurrent > maxCurrent)
swap(maxCurrent,minCurrent);
if(maxCurrent<1)
maxCurrent = 1;
//if(minCurrent>1)
// minCurrent =1;
}
return maxProduct;
}

代碼二：思路，記錄以第i個(gè)結(jié)尾的最大乘積M和最小乘積m，并且記錄這兩個(gè)區(qū)間的起點(diǎn)（終點(diǎn)都是i），不斷更新，來源http://www.51weixue.com/thread-246-1-1.html：

pair<int,int> maxproduct(double *f,int n) { //返回最大乘積的起點(diǎn)終點(diǎn)
int R = 0, r = 0; //最大最小區(qū)間的起點(diǎn)
pair<int,int> ret = make_pair(0, 0); //最大最小的區(qū)間下標(biāo)
double M = f[0], m = f[0], answer = f[0]; // 最大最小值
for (int i = 1; i < n; ++i) {
double t0 = f[i] * M, t1 = f[i] * m;
if (t0 > t1) {
M = t0;
m = t1;
}
else {
int t = R;
R = r;
r = t;
M = t1;
m = t0;
}
if (M < f[i]) {
M = f[i];
R = i;
}
if (m > f[i]) {
m = f[i];
r = i;
}
if (answer < M) {
answer = M;
ret = make_pair(R, i);
}
}
return ret;
}

解法三、
本題除了上述類似最大子數(shù)組和的解法，也可以直接用動(dòng)態(tài)規(guī)劃求解（其實(shí)，上述的解法一本質(zhì)上也是動(dòng)態(tài)規(guī)劃，只是解題所表現(xiàn)出來的具體形式與接下來的解法二不同罷了。這個(gè)不同就在于下面的解法二會(huì)寫出動(dòng)態(tài)規(guī)劃問題中經(jīng)典常見的DP方程，而解法一是直接求解）。具體解法如下：
假設(shè)數(shù)組為a[]，直接利用動(dòng)歸來求解，考慮到可能存在負(fù)數(shù)的情況，我們用Max來表示以a結(jié)尾的最大連續(xù)子串的乘積值，用Min表示以a結(jié)尾的最小的子串的乘積值，那么狀態(tài)轉(zhuǎn)移方程為：
Max=max{a, Max[i-1]*a, Min[i-1]*a};
Min=min{a, Max[i-1]*a, Min[i-1]*a};
初始狀態(tài)為Max[1]=Min[1]=a[1]。

C/C++代碼一，很簡潔的一小段代碼：

double func(double *a,const int n)
{
double *maxA = new double[n];
double *minA = new double[n];
maxA[0] = minA[0] =a[0];
double value = maxA[0];
for(int i = 1 ; i < n ; ++i)
{
maxA[i] = max(max(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
minA[i] = min(min(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
value=max(value,maxA[i]);
}
return value;
}

C/C++代碼二：

/*
給定一個(gè)浮點(diǎn)數(shù)數(shù)組，有正有負(fù)數(shù)，0，正數(shù)組成,數(shù)組下標(biāo)從1算起
求最大連續(xù)子序列乘積，并輸出這個(gè)序列，如果最大子序列乘積為負(fù)數(shù)，那么就輸出-1
用Max[i]表示以a[i]結(jié)尾乘積最大的連續(xù)子序列
用Min[i]表示以a[i]結(jié)尾乘積最小的連續(xù)子序列因?yàn)橛袕?fù)數(shù)，所以保存這個(gè)是必須的
*/
void longest_multiple(double *a,int n){
double *Min=new double[n+1]();
double *Max=new double[n+1]();
double *p=new double[n+1]();
//初始化
for(int i=0;i<=n;i++){
p[i]=-1;
}
Min[1]=a[1];
Max[1]=a[1];
double max_val=Max[1];
for(int i=2;i<=n;i++){
Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
if(max_val<Max[i])
max_val=Max[i];
}
if(max_val<0)
printf("%d",-1);
else
printf("%d",max_val);
//內(nèi)存釋放
delete [] Max;
delete [] Min;
}

C#版完整代碼(代碼來自參加英雄會(huì)在線編程挑戰(zhàn)之1019、最大乘積連續(xù)子串：http://hero.pongo.cn/Question/Details?ID=19&ExamID=19的在線提交代碼的用戶)：

//答題英雄：danielqkj
using System;
public class Test
{
void Max(double a, double b, double c)
{
double d = (a>b)?a:b;
return (d>c)?d:c;
}
void Min(double a, double b, double c)
{
double d = (a>b)?b:a;
return (d>c)?c:d;
}
public static void Main()
{
int n = Int32.parse(Console.readline());
double[] a = new double[n];
double maxvalue = a[0];
double[] max = new double[n];
double[] min = new double[n];
double start, end;
String[] s = Console.readline().split(' ');
for (int i = 0; i < n; i++)
{
a[i] = Double.parse(s[i])
}
max[0] = a[0];
min[0] = a[0];
start = 0, end = 0;
for (int i = 1; i < n; i++)
{
max[i]=Max(a[i], a[i]*max[i-1], a[i]*min[i-1]);
min[i]=Min(a[i], a[i]*max[i-1], a[i]*min[i-1]);
if (max[i] > maxvalue)
{
maxvalue = max[i];
end = i;
}
}
double mmm = maxvalue;
while ( (mmm - 0.0) > 0.00001 )
{
start = end;
mmm = mmm / a[start];
}
Console.Writeline(a[start] + " " + a[end] + " " + maxvalue);
}
}

變種

此外，此題還有另外的一個(gè)變種形式，即給定一個(gè)長度為N的整數(shù)數(shù)組，只允許用乘法，不能用除法，計(jì)算任意（N-1）個(gè)數(shù)的組合中乘積最大的一組，并寫出算法的時(shí)間復(fù)雜度。

我們可以把所有可能的（N-1）個(gè)數(shù)的組合找出來，分別計(jì)算它們的乘積，并比較大小。由于總共有N個(gè)（N-1）個(gè)數(shù)的組合，總的時(shí)間復(fù)雜度為O（N2），顯然這不是最好的解法。
OK，以下解答來自編程之美
解法1

解法2
此外，還可以通過分析，進(jìn)一步減少解答問題的計(jì)算量。假設(shè)N個(gè)整數(shù)的乘積為P，針對(duì)P的正負(fù)性進(jìn)行如下分析（其中，AN-1表示N-1個(gè)數(shù)的組合，PN-1表示N-1個(gè)數(shù)的組合的乘積）。
1.P為0

那么，數(shù)組中至少包含有一個(gè)0。假設(shè)除去一個(gè)0之外，其他N-1個(gè)數(shù)的乘積為Q，根據(jù)Q的正負(fù)性進(jìn)行討論：

Q為0
說明數(shù)組中至少有兩個(gè)0，那么N-1個(gè)數(shù)的乘積只能為0，返回0；
Q為正數(shù)
返回Q，因?yàn)槿绻?替換此時(shí)A_N_-1中的任一個(gè)數(shù)，所得到的P_N_-1為0，必然小于Q；
Q為負(fù)數(shù)
如果以0替換此時(shí)A_N_-1中的任一個(gè)數(shù)，所得到的P_N_-1為0，大于Q，乘積最大值為0。

2. P為負(fù)數(shù)

根據(jù)“負(fù)負(fù)得正”的乘法性質(zhì)，自然想到從N個(gè)整數(shù)中去掉一個(gè)負(fù)數(shù)，使得P_N_-1為一個(gè)正數(shù)。而要使這個(gè)正數(shù)最大，這個(gè)被去掉的負(fù)數(shù)的絕對(duì)值必須是數(shù)組中最小的。我們只需要掃描一遍數(shù)組，把絕對(duì)值最小的負(fù)數(shù)給去掉就可以了。

3. P為正數(shù)

類似地，如果數(shù)組中存在正數(shù)值，那么應(yīng)該去掉最小的正數(shù)值，否則去掉絕對(duì)值最大的負(fù)數(shù)值。
上面的解法采用了直接求N個(gè)整數(shù)的乘積P，進(jìn)而判斷P的正負(fù)性的辦法，但是直接求乘積在編譯環(huán)境下往往會(huì)有溢出的危險(xiǎn)（這也就是本題要求不使用除法的潛在用意），事實(shí)上可做一個(gè)小的轉(zhuǎn)變，不需要直接求乘積，而是求出數(shù)組中正數(shù)（+）、負(fù)數(shù)（-）和0的個(gè)數(shù)，從而判斷P的正負(fù)性，其余部分與以上面的解法相同。

在時(shí)間復(fù)雜度方面，由于只需要遍歷數(shù)組一次，在遍歷數(shù)組的同時(shí)就可得到數(shù)組中正數(shù)（+）、負(fù)數(shù)（-）和0的個(gè)數(shù)，以及數(shù)組中絕對(duì)值最小的正數(shù)和負(fù)數(shù)，時(shí)間復(fù)雜度為O（N）。

第二十九章、字符串編輯距離

題目描述：給定一個(gè)源串和目標(biāo)串，能夠?qū)υ创M(jìn)行如下操作：
1.在給定位置上插入一個(gè)字符
2.替換任意字符
3.刪除任意字符
寫一個(gè)程序，返回最小操作數(shù)，使得對(duì)源串進(jìn)行這些操作后等于目標(biāo)串，源串和目標(biāo)串的長度都小于2000。

提醒：上文前言中已經(jīng)說過了，此題反復(fù)出現(xiàn)，最近考的最多的是百度和Google的筆試面試經(jīng)常考察。下圖則是2013年Google的校招試題原景重現(xiàn)：

解答：

解法一、此題跟上面的最大連續(xù)乘積子串類似，常見的思路是動(dòng)態(tài)規(guī)劃，下面是簡單的DP狀態(tài)方程：

//動(dòng)態(tài)規(guī)劃：
//f[i,j]表示s[0...i]與t[0...j]的最小編輯距離。
f[i,j] = min { f[i-1,j]+1, f[i,j-1]+1, f[i-1,j-1]+(s[i]==t[j]?0:1) }
//分別表示：添加1個(gè)，刪除1個(gè)，替換1個(gè)（相同就不用替換）。

解法二、本解法來自為學(xué)論壇：http://www.51weixue.com/thread-482-1-1.html。

編輯距離的定義和計(jì)算方法如下：
Given two strings A and B, edit A to B with the minimum number of edit operations:

a) .Replace a letter with another letter
b) .Insert a letter
c) .Delete a letter

E.g.
A = interestingly _i__nterestingly
B = bioinformatics bioinformatics__
1011011011001111
Edit distance = 11
Instead of minimizing the number of edge operations, we can associate a cost function to the
operations and minimize the total cost. Such cost is called edit distance. Instead of using string edit, in computational biology, people like to use string alignment.We use similarity function, instead of cost function, to evaluate the goodness of the alignment.
E.g. of similarity function: match – 2, mismatch, insert, delete – -1.
Consider two strings ACAATCC and AGCATGC.
One of their alignment is

In the above alignment, space (‘_’) is introduced to both strings. There are 5 matches, 1
mismatch, 1 insert, and 1 delete.The alignment has similarity score 7.
A_CAATCC
AGCA_TGC
Note that the above alignment has the maximum score.Such alignment is called optimal
alignment.String alignment problem tries to find the alignment with the maximum similarity
score!String alignment problem is also called global alignment problem.
Needleman-Wunsch algorithm
Consider two strings S[1..n] and T[1..m].Define V(i, j) be the score of the optimal alignment
between S[1..i] and T[1..j].
Basis:
V(0, 0) = 0
V(0, j) = V(0, j-1) + d(_, T[j])：Insert j times
V(i, 0) = V(i-1, 0) + d(S, _)：Delete i times
that is:

Example :

下面是代碼，測試數(shù)據(jù)比較少，若有問題請指正：

//copyright@ peng_weida
//實(shí)現(xiàn)代碼如下：
//頭文件StrEditDistance.h
#pragma once
#include <string>
class CStrEditDistance
{
public:
CStrEditDistance(std::string& vStrRow, std::string& vStrColumn);
~CStrEditDistance(void);
int getScore() { return m_Score; }
int getEditDis() { return m_EditDis; }
void setEditDis(int vDis) { m_EditDis = vDis; }
void setScore(int vScore) { m_Score = vScore; }
private:
void process(const std::string& vStrRow, const std::string& vStrColumn);
int getMaxValue(int a, int b, int c)
{
if (a < b){ if (b < c) return c; return b; }
else { if (b > c) return a; return a < c ? c : a; }
}
private:
int m_EditDis;
int m_Score;
};
//源文件StrEditDistance.cpp
#include "StrEditDistance.h"
#include <iostream>
#include <iomanip>
#define MATCH 2
#define MISS_MATCH -1
#define INSERT -1
#define DELETE -1
CStrEditDistance::CStrEditDistance(std::string& vStrRow, std::string& vStrColumn)
{
process(vStrRow, vStrColumn);
}
CStrEditDistance::~CStrEditDistance(void)
{
}
//FUNCTION:
void CStrEditDistance::process(const std::string& vStrRow, const std::string& vStrColumn)
{
int editDis = 0; //編輯距離
int row = vStrColumn.length();
int column = vStrRow.length();
const int sizeR = row + 1;
const int sizeC = column + 1;
int **pScore = new int*[sizeR]; //二維指針
for (int i = 0; i <= row; i++)
pScore = new int[sizeC];
//初始化第一行和第一列
for (int c = 0; c <= column; c++)
pScore[0][c] = 0 - c;
for (int r = 0; r <= row; r++)
pScore[r][0] = 0 - r;
//從v(1,1)開始每列計(jì)算
for (int c = 1; c <= column; c++)
{
for (int r = 1; r <= row; r++)
{
//計(jì)算v(i,j)
int valueMatch;
if (vStrColumn[r-1] == vStrRow[c-1])
valueMatch = MATCH;
else
valueMatch = MISS_MATCH;
int A = pScore[r-1][c] + INSERT;
int B = pScore[r][c-1] + DELETE;
int C = pScore[r-1][c-1] + valueMatch;
pScore[r][c] = getMaxValue(A, B, C);
}
}
//計(jì)算編輯距離
int r = row, c = column;
while(r > 0 && c > 0)
{
if (pScore[r][c]+1 == pScore[r-1][c]) { editDis++; r--; continue; }
else if (pScore[r][c]+1 == pScore[r][c-1]) { editDis++; c--; continue; }
else if (pScore[r][c]+1 == pScore[r-1][c-1]){ editDis++; r--; c--; continue; }
else { r--; c--; }
}
if (r > 0 && c == 0) editDis += r;
else if (c > 0 && r == 0) editDis += c;
std::cout << std::endl;
//----------------DEBUG-------------------//
//打印數(shù)據(jù)
for (int i = 0; i <= row; i++)
{
for (int j = 0; j <= column; j++)
std::cout << std::setw(2) << pScore[j] << " ";
std::cout << std::endl;
}
std::cout << std::endl;
//設(shè)置編輯距離和得分
setEditDis(editDis);
setScore(pScore[row][column]);
for (int i = 0; i <= row; i++) //釋放內(nèi)存
{
delete pScore;
pScore = NULL;
}
delete[] pScore;
}

類似

上述問題類似于編程之美上的下述一題「以下內(nèi)容摘自編程之美第3.3節(jié)」：

許多程序會(huì)大量使用字符串。對(duì)于不同的字符串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個(gè)不相同的字符串變得相同，具體的操作方法為：

修改一個(gè)字符（如把“a”替換為“b”）；
增加一個(gè)字符（如把“abdd ”變?yōu)?#8220;aebdd ”）；
刪除一個(gè)字符（如把“travelling”變?yōu)?#8220;traveling”）。

比如，對(duì)于“abcdefg”和“abcdef ”兩個(gè)字符串來說，我們認(rèn)為可以通過增加/減少一個(gè)“g”的方式來達(dá)到目的。上面的兩種方案，都僅需要一次操作。把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離，而相似度等于“距離+1”的倒數(shù)。也就是說，“abcdefg”和“abcdef”的距離為1，相似度為1 / 2 = 0.5。
給定任意兩個(gè)字符串，你是否能寫出一個(gè)算法來計(jì)算出它們的相似度呢？

這樣，很快就可以完成一個(gè)遞歸程序，如下所示：

Int CalculateStringDistance(string strA, int pABegin, int pAEnd,
string strB, int pBBegin, int pBEnd)
{
if(pABegin > pAEnd)
{
if(pBBegin > pBEnd)
return 0;
else
return pBEnd – pBBegin + 1;
}
if(pBBegin > pBEnd)
{
if(pABegin > pAEnd)
return 0;
else
return pAEnd – pABegin + 1;
}
if(strA[pABegin] == strB[pBBegin])
{
return CalculateStringDistance(strA, pABegin + 1, pAEnd,
strB, pBBegin + 1, pBEnd);
}
else
{
int t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB,
pBBegin + 1, pBEnd);
int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd,
strB,pBBegin, pBEnd);
int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,
strB,pBBegin + 1, pBEnd);
return minValue(t1,t2,t3) + 1;
}
}

上面的遞歸程序，有什么地方需要改進(jìn)呢？問題在于：在遞歸的過程中，有些數(shù)據(jù)被重復(fù)計(jì)算了。

　　我們知道適合采用動(dòng)態(tài)規(guī)劃方法的最優(yōu)化問題中的兩個(gè)要素：最優(yōu)子結(jié)構(gòu)和重疊子問題。另外，還有一種方法稱為備忘錄（memoization），可以充分利用重疊子問題的性質(zhì)。

　　下面簡述一下動(dòng)態(tài)規(guī)劃的基本思想。和分治法一樣，動(dòng)態(tài)規(guī)劃是通過組合子問題的解而解決整個(gè)問題的。我們知道，分治算法是指將問題劃分成一睦獨(dú)立的子問題，遞歸地求解各子問題，然后合并子問題的解而得到原問題的解。與此不同，動(dòng)態(tài)規(guī)劃適用于子問題不是獨(dú)立的情況，也就是各子問題包含公共的子子問題。在這種情況下，若用分治法則會(huì)做許多不必要的工作，即重復(fù)地求解公共的子子問題。動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè)子子問題只求解一次，將其結(jié)果保存在一張表中，從而避免每次遇到各個(gè)子問題時(shí)重新計(jì)算答案。

動(dòng)態(tài)規(guī)劃通常應(yīng)用于最優(yōu)化問題。此類問題可能有很多種可行解，每個(gè)解有一個(gè)值，而我們希望找出一個(gè)具有最優(yōu)（最大或最小）值的解。稱這樣的解為該問題的“一個(gè)”最優(yōu)解（而不是“確定的”最優(yōu)解），因?yàn)榭赡艽嬖诙鄠€(gè)取最優(yōu)值的解。

　　動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)可以分為如下4個(gè)步驟：

　　1）描述最優(yōu)解的結(jié)構(gòu)。

　　2）遞歸定義最優(yōu)解的值。

　　3）按自底向上的方式計(jì)算最優(yōu)解的值。

　　4）由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解。

　　第1~3步構(gòu)成問題的動(dòng)態(tài)規(guī)劃解的基礎(chǔ)。第4步在只要求計(jì)算最優(yōu)解的值時(shí)可以略去。如果的確做了第4步，則有時(shí)要在第3步的計(jì)算中記錄一些附加信息，使構(gòu)造一個(gè)最優(yōu)解變得容易。

　　該問題明顯完全符合動(dòng)態(tài)規(guī)劃的兩個(gè)要素，即最優(yōu)子結(jié)構(gòu)和重疊子問題特性。該問題的最優(yōu)指的是兩個(gè)字符串的最短距離，子問題的重疊性可以從原書中的那個(gè)遞歸算法中看出。

　　下面再來詳細(xì)說說什么是重疊子問題。適用于動(dòng)態(tài)規(guī)劃求解的最優(yōu)化問題必須具有的第二個(gè)要素是子問題的空間要“很小”，也就是用來解原問題的遞歸算法可以反復(fù)地解同樣的子問題，而不是總在產(chǎn)生新的子問題。典型地，不同的子問題數(shù)是輸入規(guī)模的一個(gè)多項(xiàng)式。當(dāng)一個(gè)遞歸算法不斷地調(diào)用同一問題時(shí)，我們說該最優(yōu)問題包含重疊子問題。相反地，適合用分治法解決的問題只往往在遞歸的每一步都產(chǎn)生全新的問題。動(dòng)態(tài)規(guī)劃算法總是充分利用重疊子問題，即通過每個(gè)子問題只解一次，把解保存在一個(gè)需要時(shí)就可以查看的表中，而每次查表的時(shí)間為常數(shù)。

根據(jù)以上的分析，我寫了如下的動(dòng)態(tài)規(guī)劃算法：

/*DP Algorithm
　 * A loop method using dynamic programming.
　 * Calculate from bottom to top.
　 */
 int calculateStringDistance(string strA, string strB)
 {
　　　　 int lenA = (int)strA.length();
　　　　 int lenB = (int)strB.length();
　　　　 int c[lenA+1][lenB+1]; 
        // Record the distance of all begin points of each string
        //初始化方式與背包問題有點(diǎn)不同
　　　　 for(int i = 0; i < lenA; i++) c[i][lenB] = lenA - i;
　　　　 for(int j = 0; j < lenB; j++) c[lenA][j] = lenB - j;
　　　　 c[lenA][lenB] = 0;
　　　　 for(int i = lenA-1; i >= 0; i--)
　　　　　　　　 for(int j = lenB-1; j >= 0; j--)
　　　　　　　　 {
　　　　　　　　　　　　 if(strB[j] == strA[i])
　　　　　　　　　　　　　　　　 c[i][j] = c[i+1][j+1];
　　　　　　　　　　　　 else
　　　　　　　　　　　　　　　　 c[i][j] = minValue(c[i][j+1], c[i+1][j], c[i+1][j+1]) + 1;
　　　　　　　　 }
 
　　　　 return c[0][0];
 }

深入

詳細(xì)讀者朋友們也已經(jīng)看到了，百度/Google經(jīng)常喜歡出這個(gè)字符串編輯距離，實(shí)際上，關(guān)于這個(gè)“編輯距離”問題在搜索引擎中有著重要的作用，如搜索引擎關(guān)鍵字查詢中拼寫錯(cuò)誤的提示，如下圖所示，當(dāng)你輸入“Jult”后，因?yàn)闆]有這個(gè)單詞“Jult”，所以搜索引擎猜測你可能是輸入錯(cuò)誤，進(jìn)而會(huì)提示你是不是找“July”：
但這個(gè)拼寫錯(cuò)誤檢查的原理是什么呢？Google是基于貝葉斯統(tǒng)計(jì)推斷的方法，相關(guān)原理詳情可以看下Google的研發(fā)總監(jiān)Peter Norvig寫的這篇文章：http://norvig.com/spell-correct.html，以及fuanyif寫的這篇：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。
關(guān)于什么是“編輯距離”：一個(gè)快速、高效的Levenshtein算法實(shí)現(xiàn)，這個(gè)是計(jì)算兩個(gè)字符串的算法，Levenshtein距離又稱為“編輯距離”，是指兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)換成另一個(gè)所需的最少編輯操作次數(shù)。當(dāng)然，次數(shù)越小越相似。這里有一個(gè)BT樹的數(shù)據(jù)結(jié)構(gòu)，挺有意思的：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees；
最后，Lucene中也有這個(gè)算法的實(shí)現(xiàn)(我想，一般的搜索引擎一般都應(yīng)該會(huì)有此項(xiàng)拼寫錯(cuò)誤檢查功能的實(shí)現(xiàn))，下面是lucene的源碼(并沒有太多優(yōu)化，與實(shí)際工程中java注重實(shí)用性的原則并不背離)：
1. public final class LevensteinDistance {
3. public LevensteinDistance () {
4. }
6. // Compute Levenshtein distance:
7. // see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String)
9. public float getDistance (String target, String other) {
10. char[] sa;
11. int n;
12. int p[];
13. //'previous' cost array, horizontally
14. int d[];
15. // cost array, horizontally
16. int _d[];
17. //placeholder to assist in swapping p and d
19. sa = target.toCharArray();
20. n = sa.length;
21. p = new int[n+1];
22. d = new int[n+1];
24. final int m = other.length();
25. if (n == 0 || m == 0) {
26. if (n == m) {
27. return 1;
28. }
29. else {
30. return 0;
31. }
32. }
34. // indexes into strings s and t
35. int i;
36. // iterates through s
37. int j;
38. // iterates through t
40. char t_j;
41. // jth character of t
43. int cost;
44. // cost
46. for (i = 0; i<=n; i++) {
47. p[i] = i;
48. }
50. for (j = 1; j<=m; j++) {
51. t_j = other.charAt(j-1);
52. d[0] = j;
54. for (i=1; i<=n; i++) {
55. cost = sa[i-1]==t_j ? 0 : 1;
57. // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
58. d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
59. }
62. // copy current distance counts to 'previous row' distance counts
63. _d = p;
64. p = d;
65. d = _d;
66. }
69. // our last action in the above loop was to switch d and p, so p now
71. // actually has the most recent cost counts
72. return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
73. }
75. }

擴(kuò)展

當(dāng)然，面試官還可以繼續(xù)問下去，如請問，如何設(shè)計(jì)一個(gè)比較兩篇文章相似性的算法？這個(gè)問題的討論可以看看這里：http://t.cn/zl82CAH。OK，字符串編輯距離這個(gè)問題實(shí)用性很強(qiáng)，限于篇幅，詳情讀者自己深入吧。

只有注冊用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 程序員編程藝術(shù)-----第二十八 ~ 二十九章-----最大連續(xù)乘積子串、字符串編輯距離程序員編程藝術(shù)-----第二十七章-----不改變正負(fù)數(shù)相對(duì)順序重新排列數(shù)組程序員編程藝術(shù)-----第二十五章-----二分查找實(shí)現(xiàn)（Jon Bentley：90%程序員無法正確實(shí)現(xiàn)）程序員編程藝術(shù)-----第二十三 ~ 二十四章-----楊氏矩陣、不重復(fù)Hash編碼程序員編程藝術(shù)-----第十五 ~ 二十章-----全排列、跳臺(tái)階、奇偶、第一個(gè)出現(xiàn)一次字符、一致性hash 程序員編程藝術(shù)-----第十一 ~ 十四章-----海量整數(shù)處理、蓄水池抽樣、回文程序員編程藝術(shù)-----第十章-----最長公共子序列(LCS)問題程序員編程藝術(shù)-----第九章-----閑話鏈表追趕問題程序員編程藝術(shù)-----第八章-----從頭至尾漫談虛函數(shù) 程序員編程藝術(shù)-----第七章-----求連續(xù)子數(shù)組的最大和

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

mysileng

導(dǎo)航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

程序員編程藝術(shù)-----第二十八 ~ 二十九章-----最大連續(xù)乘積子串、字符串編輯距離

第二十八~二十九章：最大連續(xù)乘積子串、字符串編輯距離

前言

第二十八章、最大連續(xù)乘積子串

變種

第二十九章、字符串編輯距離

類似

深入

擴(kuò)展