有 n 个公交车站，我们知道第 i 站和第 j 站之间的费用。 这是一条单行道。考虑到所有可能的连接，从第 1 站到第 n 站的路线的最低价格是多少？时间和内存消耗应该尽可能少。
附注举个例子，假设有 4 个站点。我们有这样一张价格表:
. 3$ 5$ 7$ . . 1$ 3$ . . . 1$
从第 1 站到第 4 站不停歇，我们支付 7 美元。如果我们在第二站改变路线，我们需要支付 3$+1$ = 4$ 才能开到第三站，但是如果我们走到终点，我们会多付 2$，所以总的来说会花费 6$，但是如果我们再次在第 3 站更改路线，我们将支付 4+1=5$。
最佳答案
设 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 指出的那样，这是最佳的。)
关于algorithm - 有趣的最低价格问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4814265/