# 1687. Delivering Boxes from Storage to Ports        • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: int boxDelivering(vector>& boxes, int portsCount, int maxBoxes, int maxWeight) { const int n = boxes.size(); // dp[i] := min trips to deliver boxes[0..i) and return to the storage vector dp(n + 1); int trips = 2; int weight = 0; for (int l = 0, r = 0; r < n; ++r) { weight += boxes[r]; // current box is different from previous one, need to make one more trip if (r > 0 && boxes[r] != boxes[r - 1]) ++trips; while (r - l + 1 > maxBoxes || weight > maxWeight || // loading boxes[l] in the previous turn is always no bad than // loading it in this turn (l < r && dp[l + 1] == dp[l])) { weight -= boxes[l]; if (boxes[l] != boxes[l + 1]) --trips; ++l; } // min trips to deliver boxes[0..r] // = min trips to deliver boxes[0..l) + trips to deliver boxes[l..r] dp[r + 1] = dp[l] + trips; } return dp[n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) { final int n = boxes.length; // dp[i] := min trips to deliver boxes[0..i) and return to the storage int[] dp = new int[n + 1]; int trips = 2; int weight = 0; for (int l = 0, r = 0; r < n; ++r) { weight += boxes[r]; // current box is different from previous one, need to make one more trip if (r > 0 && boxes[r] != boxes[r - 1]) ++trips; while (r - l + 1 > maxBoxes || weight > maxWeight || // loading boxes[l] in the previous turn is always no bad than // loading it in this turn (l < r && dp[l + 1] == dp[l])) { weight -= boxes[l]; if (boxes[l] != boxes[l + 1]) --trips; ++l; } // min trips to deliver boxes[0..r] // = min trips to deliver boxes[0..l) + trips to deliver boxes[l..r] dp[r + 1] = dp[l] + trips; } return dp[n]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution: def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int: n = len(boxes) # dp[i] := min trips to deliver boxes[0..i) and return to the storage dp =  * (n + 1) trips = 2 weight = 0 l = 0 for r in range(n): weight += boxes[r] # current box is different from previous one, need to make one more trip if r > 0 and boxes[r] != boxes[r - 1]: trips += 1 # loading boxes[l] in the previous turn is always no bad than loading it in this turn while r - l + 1 > maxBoxes or weight > maxWeight or (l < r and dp[l + 1] == dp[l]): weight -= boxes[l] if boxes[l] != boxes[l + 1]: trips -= 1 l += 1 # min trips to deliver boxes[0..r] # = min trips to deliver boxes[0..l) + trips to deliver boxes[l..r] dp[r + 1] = dp[l] + trips return dp[n]