在路上，有些地方散落着金币。对于每一枚硬币，它的位置是已知的，它由一个整数给出——距起点的距离（以米为单位）。 所有硬币都位于起点的右侧，距离起点不同。阿里巴巴沿着路跑并收集硬币，从时间 0 开始。他每秒跑一米。每个硬币都有一个截止日期，必须在截止日期之前将其捡起，否则硬币将消失。阿里巴巴必须在最短的时间内收集所有的硬币。他可以从线上的任何一点开始，以任何顺序收集硬币，但他必须绝对收集所有硬币并尽量减少这样做所花费的时间。
最坏的情况是O(n^2)，其中n是硬币的数量。
这个问题可以做的陈述：
For any subsequence of coins, we will finish collecting coins either on the last or on the first one.
一开始，我们可以考虑小的子问题。
If n = 1，那么只有一枚硬币，存在多久都无所谓，因为我们可以从任何硬币开始。因此，答案是0秒。
If n = 2，为了清楚起见，让我们依次表示硬币 1 和 2。那么有两种可能的情况：我们按照1->2或者2->1的顺序收集硬币。对于每一种情况，我们都需要考虑时间。如果 2.time - 1.time >= dist(2,1)，那么我们可以从第一个跳到第二个，反之亦然。
We can also reason about problems of larger size。我知道我们需要跟踪我们完成了哪个硬币，但是我不明白如何从子问题过渡到更大的问题，以便为这个问题建立递归关系。