题目分析
本题类似01背包问题，可以使用线性DP求解，用dp[i]表示前i个箱子需要的最少行程次数，那么可得dp[i] = Math.min(dp[i], dp[j - 1] + cost(j, i))，其中cost(j, i)表示用一辆车运送从j到i的箱子的花费。
动态规划
上述算法虽然能求解本题，但是要遍历n个物品，每个物品要遍历j，即最后一趟可以运送从j到i的所有货物。在确定i和j后，还需要O(n)的时间计算cost(i, j)。
算法的时间复杂度为O(n^3)，空间复杂度为O(n)。
虽然可以使用前缀和优化cost(i, j)变成O(1)，但是仍然是$O(n^2)$的时间复杂度，对于1e5的数据量，也是会超时的。
1 |
单调队列
上述算法虽然能求解本题，但是要遍历n个物品，每个物品要遍历j，即最后一趟可以运送从j到i的所有货物。在确定i和j后，还需要O(n)的时间计算cost(i, j)。
算法的时间复杂度为O(n^3)，空间复杂度为O(n)。
虽然可以使用前缀和优化cost(i, j)变成O(1)，但是仍然是$O(n^2)$的时间复杂度，对于1e5的数据量，也是会超时的。
1 |
刷题总结
这个题目思路容易想，但是能优化到二维是不容易的，希望小伙伴多多练习，一定要把动态规划拿下。