对于悬崖上连续的三个点,它们构成的形状可以分为两类:“<”形(高点与低点的连线不穿过悬崖)与 “>”形。 (高点与低点的连线穿过了悬崖) 对于“>”形,从顶端到达底端的最短路径就是顺着形状走,而对于“<”形状,从顶端到达底端的最短路径可以忽 略中间的点,即顶端到底端的连线。 所以最短的路径应当是许多“>”形组成的形状,并且只要构成了这种形状,那么在路径中任取三个点,它们构成 的也都是“>”形。 假设我们已经求出了一条从0到i的最短路径a[0...j],那么从0到i+1的最短路径只需要考虑a[j-1]、a[j]与 i+1三个点所构成的形状。若为“>”形,...