Press "Enter" to skip to content

Posts tagged as “dp”

花花酱 LeetCode 1691. Maximum Height by Stacking Cuboids

Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Example 1:

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.

Example 2:

Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

Example 3:

Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
Output: 102
Explanation:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.

Constraints:

  • n == cuboids.length
  • 1 <= n <= 100
  • 1 <= widthi, lengthi, heighti <= 100

Solution: Math/Greedy + DP

Direct DP is very hard, since there is no orders.

We have to find some way to sort the cuboids such that cuboid i can NOT stack on cuboid j if i > j. Then dp[i] = max(dp[j]) + height[i], 0 <= j < i, for each i, find the best base j and stack on top of it.
ans = max(dp)

We can sort the cuboids by their sorted dimensions, and cuboid i can stack stack onto cuboid j if and only if w[i] <= w[j] and l[i] <= l[j] and h[i] <= h[j].

First of all, we need to prove that all heights must come from the largest dimension of each cuboid.

1. If the top of the stack is A1*A2*A3, A3 < max(A1, A2), we can easily swap A3 with max(A1, A2), it’s still stackable but we get larger heights.
e.g. 3x5x4, base is 3×5, height is 4, we can rotate to get base of 3×4 with height of 5.

2. If a middle cuboid A of size A1*A2*A3, assuming A1 >= A2, A1 > A3, on top of A we have another cuboid B of size B1*B2*B3, B1 <= B2 <= B3.
We have A1 >= B1, A2 >= B2, A3 >= B3, by rotating A we have A3*A2*A1
A3 >= B3 >= B1, A2 >= B2, A1 > A3 >= B3, so B can be still on top of A, and we get larger height.

e.g. A: 3x5x4, B: 2x3x4
A -> 3x4x5, B is still stackable.

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

花花酱 LeetCode 1690. Stone Game VII

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player’s turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones’ values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob’s score if they both play optimally.

Example 1:

Input: stones = [5,3,1,4,2]
Output: 6
Explanation: 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.

Example 2:

Input: stones = [7,90,5,1,100,10,10,2]
Output: 122

Constraints:

  • n == stones.length
  • 2 <= n <= 1000
  • 1 <= stones[i] <= 1000

Solution: MinMax + DP

For a sub game of stones[l~r] game(l, r), we have two choices:
Remove the left one: sum(stones[l + 1 ~ r]) – game(l + 1, r)
Remove the right one: sum(stones[l ~ r – 1]) – game(l, r – 1)
And take the best choice.

Time complexity: O(n^2)
Space complexity: O(n^2)

C++/Top Down

C++/Bottom-Up

Python3

Related Problems

花花酱 LeetCode 1687. Delivering Boxes from Storage to Ports

You have the task of delivering some boxes from storage to their ports using only one ship. However, this ship has a limit on the number of boxes and the total weight that it can carry.

You are given an array boxes, where boxes[i] = [ports​​i​, weighti], and three integers portsCountmaxBoxes, and maxWeight.

  • ports​​i is the port where you need to deliver the ith box and weightsi is the weight of the ith box.
  • portsCount is the number of ports.
  • maxBoxes and maxWeight are the respective box and weight limits of the ship.

The boxes need to be delivered in the order they are given. The ship will follow these steps:

  • The ship will take some number of boxes from the boxes queue, not violating the maxBoxes and maxWeight constraints.
  • For each loaded box in order, the ship will make a trip to the port the box needs to be delivered to and deliver it. If the ship is already at the correct port, no trip is needed, and the box can immediately be delivered.
  • The ship then makes a return trip to storage to take more boxes from the queue.

The ship must end at storage after all the boxes have been delivered.

Return the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.

Example 1:

Input: boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
Output: 4
Explanation: The optimal strategy is as follows: 
- The ship takes all the boxes in the queue, goes to port 1, then port 2, then port 1 again, then returns to storage. 4 trips.
So the total number of trips is 4.
Note that the first and third boxes cannot be delivered together because the boxes need to be delivered in order (i.e. the second box needs to be delivered at port 2 before the third box).

Example 2:

Input: boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
Output: 6
Explanation: The optimal strategy is as follows: 
- The ship takes the first box, goes to port 1, then returns to storage. 2 trips.
- The ship takes the second, third and fourth boxes, goes to port 3, then returns to storage. 2 trips.
- The ship takes the fifth box, goes to port 3, then returns to storage. 2 trips.
So the total number of trips is 2 + 2 + 2 = 6.

Example 3:

Input: boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
Output: 6
Explanation: The optimal strategy is as follows:
- The ship takes the first and second boxes, goes to port 1, then returns to storage. 2 trips.
- The ship takes the third and fourth boxes, goes to port 2, then returns to storage. 2 trips.
- The ship takes the fifth and sixth boxes, goes to port 3, then returns to storage. 2 trips.
So the total number of trips is 2 + 2 + 2 = 6.

Example 4:

Input: boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
Output: 14
Explanation: The optimal strategy is as follows:
- The ship takes the first box, goes to port 2, then storage. 2 trips.
- The ship takes the second box, goes to port 2, then storage. 2 trips.
- The ship takes the third and fourth boxes, goes to port 3, then storage. 2 trips.
- The ship takes the fifth box, goes to port 3, then storage. 2 trips.
- The ship takes the sixth and seventh boxes, goes to port 3, then port 4, then storage. 3 trips. 
- The ship takes the eighth and ninth boxes, goes to port 1, then port 5, then storage. 3 trips.
So the total number of trips is 2 + 2 + 2 + 2 + 3 + 3 = 14.

Constraints:

  • 1 <= boxes.length <= 105
  • 1 <= portsCount, maxBoxes, maxWeight <= 105
  • 1 <= ports​​i <= portsCount
  • 1 <= weightsi <= maxWeight

Solution: Sliding Window

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1681. Minimum Incompatibility

You are given an integer array nums​​​ and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset’s incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.

Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.

Constraints:

  • 1 <= k <= nums.length <= 16
  • nums.length is divisible by k
  • 1 <= nums[i] <= nums.length

Solution: TSP

dp[s][i] := min cost to distribute a set of numbers represented as a binary mask s, the last number in the set is the i-th number.

Init:
1.dp[*][*] = inf
2. dp[1 <<i][i] = 0, cost of selecting a single number is zero.

Transition:
1. dp[s | (1 << j)][j] = dp[s][i] if s % (n / k) == 0, we start a new group, no extra cost.
2. dp[s | (1 << j)][j] = dp[s][i] + nums[j] – nums[i] if nums[j] > nums[i]. In the same group, we require the selected numbers are monotonically increasing. Each cost is nums[j] – nums[i].
e.g. 1, 3, 7, 20, cost is (3 – 1) + (7 – 3) + (20 – 7) = 20 – 1 = 19.

Ans: min(dp[(1 << n) – 1])

Time complexity: O(2^n * n^2)
Space complexity: O(2^n * n)

C++

花花酱 LeetCode 1671. Minimum Number of Removals to Make Mountain Array

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Example 3:

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4

Example 4:

Input: nums = [1,2,3,4,4,3,2,1]
Output: 1

Constraints:

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 109
  • It is guaranteed that you can make a mountain array out of nums.

Solution: DP / LIS

LIS[i] := longest increasing subsequence ends with nums[i]
LDS[i] := longest decreasing subsequence starts with nums[i]
Let nums[i] be the peak, the length of the mountain array is LIS[i] + LDS[i] – 1
Note: LIS[i] and LDS[i] must be > 1 to form a valid mountain array.
ans = min(n – (LIS[i] + LDS[i] – 1)) 0 <= i < n

Time complexity: O(n^2)
Space complexity: O(n)

C++