有趣的最低价格问题

Question

有n个公共汽车站,我们知道第i和第j站之间的费用.这是一条单行道.考虑到所有可能的连接,从第1站到第n站的路线的最低价格是多少？时间和内存消耗应尽可能少.

ps举一个例子,比方说,有4站.我们有这样的价格表:

. 3$ 5$ 7$
. .  1$ 3$
. .  .  1$

从1-st到4-th,我们支付7 $.如果我们改变在第二站的路线,我们支付3 $ + 1 $ = 4 $把车开到第三站,但我们付出2 $更多,如果我们走到最后,所以整体成本会$ 6,但同样,如果我们改变第3站的路线,我们将支付4 + 1 = 5 $.

Answer 1

让我们d[i][j]在给定的价格,l[k]从去最小的综合成本k来n.然后

l[n] = 0

l[k] = min(d[k][i] + l[i], i=k+1..n)

运行时间为O(n ^ 2).(并且,正如@Henrik指出的那样,它是最佳的.)