問(wèn)題描述
假設(shè)你正在學(xué)習(xí)用吉他彈一首曲子,這首曲子的吉他譜是長(zhǎng)度為n的數(shù)組notes,其中每一個(gè)元素代表一個(gè)音符,每個(gè)音符都需要你用一只手的一根手指(只考慮單手,并且手指數(shù)量為F)去按不同的品位,假設(shè)不同品位之間的切換是有難度的,難度的函數(shù)定義為d(f,notes[i],g,notes[i+1]),代表從手指f彈奏notes[i]切換到手指g彈奏notes[i+1]的難度,現(xiàn)在我們以最輕松的姿勢(shì)完成這首曲子, 我們應(yīng)該怎么做?
初步設(shè)想
subproblems
怎么彈奏notes[i]音符
guess
用哪根手指f彈奏notes[i]
recurrence
for f,g in F
DP(i) = min(DP(i+1) + d(f, notes[i], g, notes[i + 1]));
上面的遞歸表達(dá)式看上去像那么回事,但是實(shí)際上是錯(cuò)的.
因?yàn)镈P(i+1)代表彈奏notes[i+1]的最小難度,但是d(f, notes[i], g, notes[i + 1])代表的是使用f彈奏notes[i]轉(zhuǎn)移到使用g彈奏notes[i+1]的難度,所以DP(i+1) + d(f, notes[i], g, notes[i + 1])這兩者相加毫無(wú)意義,因?yàn)镈P(i+1)并不是使用手指g彈奏notes[i+1]的最小難度.
重新思考
subproblems
使用哪根手指f彈奏音符notes[i]
guess
使用哪根手指g彈奏音符notes[i+1]
recurrence
for g in F
DP(i,f) = min(DP(i+1, g) + d(f, notes[i], g, notes[i + 1]));
is topological order?
如上圖所示,橫軸代表音符,縱軸代表手指(假設(shè)有5根手指),將上圖想象成一個(gè)5*5的矩陣A, A(1,1)代表用第1個(gè)手指彈奏第1個(gè)音符,依次類推.
將上圖看成一個(gè)圖的話,V是手指和音符的組合,一共n*F個(gè)vertices,每一個(gè)edge則代表轉(zhuǎn)移的難度,edge的weight則是d(f,notes[i],g,notes[i+1])的值,那么要求難度最小的演奏方法,就是求這個(gè)圖的最短路徑.而且顯而易見(jiàn),這個(gè)圖是DAG.
Are we solving the original problem?
但是這并不是我們熟知的single source shortest path問(wèn)題,笨一點(diǎn)的辦法是求5次單源最短路徑,再?gòu)钠渲腥∽钚〉闹?更聰明的做法是加入一個(gè)額外的節(jié)點(diǎn),并且這個(gè)節(jié)點(diǎn)到所有A(F,1)節(jié)點(diǎn)的邊的weight都為0,如下圖:
time complexity
#subproblem=n*F
每個(gè)subproblem的耗時(shí)=F(嘗試使用每一個(gè)手指彈奏notes[i+1])
那么該算法的時(shí)間復(fù)雜度為:,因?yàn)镕代表手指,可以看成是常數(shù)項(xiàng),那么實(shí)際上該算法的復(fù)雜度可以看作是
