问题描述
假设你正在学习用吉他弹一首曲子,这首曲子的吉他谱是长度为n的数组notes,其中每一个元素代表一个音符,每个音符都需要你用一只手的一根手指(只考虑单手,并且手指数量为F)去按不同的品位,假设不同品位之间的切换是有难度的,难度的函数定义为d(f,notes[i],g,notes[i+1]),代表从手指f弹奏notes[i]切换到手指g弹奏notes[i+1]的难度,现在我们以最轻松的姿势完成这首曲子, 我们应该怎么做?
初步设想
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]));
上面的递归表达式看上去像那么回事,但是实际上是错的.
因为DP(i+1)代表弹奏notes[i+1]的最小难度,但是d(f, notes[i], g, notes[i + 1])代表的是使用f弹奏notes[i]转移到使用g弹奏notes[i+1]的难度,所以DP(i+1) + d(f, notes[i], g, notes[i + 1])这两者相加毫无意义,因为DP(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?
如上图所示,横轴代表音符,纵轴代表手指(假设有5根手指),将上图想象成一个5*5的矩阵A, A(1,1)代表用第1个手指弹奏第1个音符,依次类推.
将上图看成一个图的话,V是手指和音符的组合,一共n*F个vertices,每一个edge则代表转移的难度,edge的weight则是d(f,notes[i],g,notes[i+1])的值,那么要求难度最小的演奏方法,就是求这个图的最短路径.而且显而易见,这个图是DAG.
Are we solving the original problem?
但是这并不是我们熟知的single source shortest path问题,笨一点的办法是求5次单源最短路径,再从其中取最小的值,更聪明的做法是加入一个额外的节点,并且这个节点到所有A(F,1)节点的边的weight都为0,如下图:
time complexity
#subproblem=n*F
每个subproblem的耗时=F(尝试使用每一个手指弹奏notes[i+1])
那么该算法的时间复杂度为:,因为F代表手指,可以看成是常数项,那么实际上该算法的复杂度可以看作是
