Readme

1687.Delivering-Boxes-from-Storage-to-Ports

我们先来考察一下贪心的解法为什么会有局限性。我们考察从第一个盒子开始，假设到第5个盒子为止，区间[1:5]是用一次船载的极限（考虑了盒子总数、盒子总重的约束）。

idx   1 2 3 4 5
port: 1 2 3 4 5 

在上面的例子中总共需要6段航程（包括回港）。那么为什么我们充分利用了船载极限，不见得是最优解呢？其实是和之后的行程有关系。看下面的例子：

idx   1 2 3 4 5 6
port: 1 2 3 4 5 5

如果按照之前的方案，我们需要两次船载，分别是运载[1:5]，需要6段trip，然后运载[6]，需要2段trip。总共需要8段trip。但是更优的方案是，第一次运载[1:4]，需要5段trip；第二次运载[5:6]需要2段trip，总共就是7段trip。

我们发现了什么？第一种贪心方案，会使得port 5的两个箱子被拆分成了两次船载来运输，中间白白浪费了一次回港的trip。而更优的方案是，我们不使用船载的极限，而是把盒子5的机会留到下一次船载，使得第二次出船的时候，一次就把两个箱子都运走。这就是为什么极限贪心的方法不是最优解的原因。

于是我们拓展一下，考虑当前这船的货物，从第i个箱子开始，船载极限允许最多装到第j个箱子。令dp[x]表示运送前i个盒子最少需要的trip数目。

idx    i .....   j j+1
port   X X X X X X  X

第一种方案，就是极限贪心。如下图，我们可以知道dp[j] = dp[i-1] + tripNums[i:j] + 1，其中tripNums[i:j]就是从仓库出发依次走完i~j所在港口数目，最后一个1是回港的trip。

idx    i .....   j j+1
port  [X X X X X X] X

第二种方案，就是当返现j+1和j的盒子属于同一个港口的时候，退让一部分容量，将与j+1相同港口的盒子都留到下一次去。假设箱子j-1、j都是与j+1同港口的，那么我们就有dp[j-2] = dp[i-1] + tripNums[i:j-2] + 1

idx    i ..... j-1 j j+1
port  [X X X X] Y  Y Y

注意，我们为什么不把断点设置在j-1和j之间呢？原因是，那样做的话并没有起到预期的节省trip的作用，到达Y港口的次数依然被割裂为两次出海。与其这样没有起到节省trip的效果，那还不如第一种方案，把船载容量用到极限。

所以总结一下，如果我们从i个箱子开始装船，那么其实就两种方案。第一种方案就是用来船载的极限，装到箱子j为止，这样我们就可以更新dp[j]。第二种方案，就是发现如果箱子j和箱子j+1在同一个港口，那么我们往前回溯同一个港口的连续的箱子直至j'，于是我们更新dp[j'-1]。

这里我们有一个疑问，那么处于i和j之间的这些dp，我们并没有更新到，这有问题吗？其实没有问题，对于我们没有更新到的dp[x]，意味着以x为船载最后一箱的方案并不是optimal的。事实上，我们只依据之前的两种方案去做装载分配的话，永远不会产生这样的情况。

此外，还有一个问题。我们永远按照这两种方案去做，那么一定能更新到最后一个箱子的dp[n]吗？答案是的。第一种极限贪心可以保证装到最后一个箱子（即使没有到船载极限），并在遍历到最后一个箱子时更新dp[n]。