Posts published in “Dynamic Programming”

花花酱 LeetCode 2008. Maximum Earnings From Taxi

By zxi on November 26, 2021

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [start_i, end_i, tip_i] denotes the i^th passenger requesting a ride from point start_i to point end_i who is willing to give a tip_i dollar tip.

For each passenger i you pick up, you earn end_i - start_i + tip_i dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

Constraints:

1 <= n <= 10⁵
1 <= rides.length <= 3 * 10⁴
rides[i].length == 3
1 <= start_i < end_i <= n
1 <= tip_i <= 10⁵

Solution: DP

dp[i] := max earnings we can get at position i and the taxi is empty.

dp[i] = max(dp[i – 1], dp[s] + gain) where e = i, gain = e – s + tips

For each i, we check all the rides that end at i and find the best one (which may have different starting points), otherwise the earning will be the same as previous position (i – 1).

answer = dp[n]

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

C++

// Author: Huahua

class Solution {

public:

long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {

vector<long long> dp(n + 1);

vector<vector<pair<int, int>>> m(n + 1);

for (const auto& r : rides)

m[r[1]].emplace_back(r[0], r[1] - r[0] + r[2]);

for (int i = 1; i <= n; ++i) {

dp[i] = dp[i - 1];

for (const auto [s, g] : m[i])

dp[i] = max(dp[i], dp[s] + g);

}

return dp[n];

}

};

花花酱 LeetCode 1883. Minimum Skips to Arrive at Meeting On Time

By zxi on August 8, 2021

You are given an integer hoursBefore, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through n roads. The road lengths are given as an integer array dist of length n, where dist[i] describes the length of the i^th road in kilometers. In addition, you are given an integer speed, which is the speed (in km/h) you will travel at.

After you travel road i, you must rest and wait for the next integer hour before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.

For example, if traveling a road takes 1.4 hours, you must wait until the 2 hour mark before traveling the next road. If traveling a road takes exactly 2 hours, you do not need to wait.

However, you are allowed to skip some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.

For example, suppose traveling the first road takes 1.4 hours and traveling the second road takes 0.6 hours. Skipping the rest after the first road will mean you finish traveling the second road right at the 2 hour mark, letting you start traveling the third road immediately.

Return the minimum number of skips required to arrive at the meeting on time, or -1 if it is impossible.

Example 1:

Input: dist = [1,3,2], speed = 4, hoursBefore = 2
Output: 1
Explanation:
Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours.
You can skip the first rest to arrive in ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 hours.
Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.

Example 2:

Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10
Output: 2
Explanation:
Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours.
You can skip the first and third rest to arrive in ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 hours.

Example 3:

Input: dist = [7,3,5,5], speed = 1, hoursBefore = 10
Output: -1
Explanation: It is impossible to arrive at the meeting on time even if you skip all the rests.

Constraints:

n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 10⁵
1 <= speed <= 10⁶
1 <= hoursBefore <= 10⁷

Solution: DP

Let dp[i][k] denote min (time*speed) to finish the i-th road with k rest.

dp[i][k] = min(dp[i – 1][k – 1] + dist[i] / speed * speed, # skip the rest,
(dp[i-1][k] + dist[i] + speed – 1) // speed * speed # rest

ans = argmin(dp[n][k] <= hours * speed)

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

C++

// Author: Huahua

class Solution {

public:

int minSkips(vector<int>& dist, int speed, int hoursBefore) {

const int n = dist.size();

const long total = accumulate(begin(dist), end(dist), 0L);

if (total > static_cast<long>(speed) * hoursBefore) return -1;

vector<vector<long>> dp(n + 1, vector<long>(n + 1, LONG_MAX / 2));

dp[0][0] = 0;

for (int i = 1; i <= n; ++i)

for (int k = 0; k <= i; ++k)

dp[i][k] = min((dp[i - 1][k] + dist[i - 1] + speed - 1) / speed * speed,

(k ? dp[i - 1][k - 1] + dist[i - 1] : LONG_MAX));

for (int k = 0; k < n; ++k)

if (dp[n][k] <= static_cast<long>(speed) * hoursBefore) return k;

return -1;

}

};

Python3

// Author: Huahua

class Solution:

def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:

if sum(dist) > speed * hoursBefore: return -1

@cache

def dp(i: int, k: int):

if k < 0: return float('inf')

if i < 0: return 0

return min((dp(i - 1, k) + dist[i] + speed - 1) // speed * speed,

dp(i - 1, k - 1) + dist[i])

n = len(dist)

for k in range(n):

if dp(n - 1, k) <= speed * hoursBefore: return k

return -1

花花酱 LeetCode 1879. Minimum XOR Sum of Two Arrays

By zxi on August 7, 2021

You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).

For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return the XOR sum after the rearrangement.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

Solution: DP / Permutation to combination

dp[s] := min xor sum by using a subset of nums2 (presented by a binary string s) xor with nums1[0:|s|].

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

C++

// Author: Huahua

class Solution {

public:

int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {

const int n = nums1.size();

vector<int> dp(1 << n, INT_MAX);

dp[0] = 0;

for (int s = 0; s < 1 << n; ++s) {

int index = __builtin_popcount(s);

for (int i = 0; i < n; ++i) {

if (s & (1 << i)) continue;

dp[s | (1 << i)] = min(dp[s | (1 << i)],

dp[s] + (nums1[index] ^ nums2[i]));

}

return dp.back();

}

};

花花酱 LeetCode 1872. Stone Game VIII

By zxi on August 5, 2021

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, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones’ values to the player’s score.
Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice’s goal is to maximize the score difference, and Bob’s goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

Constraints:

n == stones.length
2 <= n <= 10⁵
-10⁴ <= stones[i] <= 10⁴

Solution: Prefix Sum + DP

Note: Naive DP (min-max) takes O(n²) which leads to TLE. The key of this problem is that each player takes k stones, but put their sum back as a new stone, so you can assume all the original stones are still there, but opponent has to start from the k+1 th stone.

Let dp[i] denote the max score diff that current player can achieve by taking stones[0~i] (or equivalent)

dp[n-1] = sum(A[0~n-1]) // Alice takes all the stones.
dp[n-2] = sum(A[0~n-2]) – (A[n-1] + sum(A[0~n-2])) = sum(A[0~n-2]) – dp[n-1] // Alice takes n-1 stones, Bob take the last one (A[n-1]) + put-back-stone.
dp[n-3] = sum(A[0~n-3]) – max(dp[n-2], dp[n-1]) // Alice takes n-2 stones, Bob has two options (takes n-1 stones or takes n stones)
…
dp[0] = A[0] – max(dp[n-1], dp[n-1], …, dp[1]) // Alice takes the first stone, Bob has n-1 options.

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

C++

// Author: Huahua

class Solution {

public:

int stoneGameVIII(vector<int>& stones) {

const int n = stones.size();

for (int i = 1; i < n; ++i)

stones[i] += stones[i - 1];

int ans = stones.back(); // take all the stones.

for (int i = n - 2; i > 0; --i)

ans = max(ans, stones[i] - ans);

return ans;

}

};

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

By zxi on August 4, 2021

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 10⁹+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

Constraints:

1 <= n <= 1000
1 <= k <= n

Solution: DP

dp(n, k) = dp(n – 1, k – 1) + (n-1) * dp(n-1, k)

Time complexity: O(n*k)
Space complexity: O(n*k) -> O(k)

C++

// Author: Huahua

class Solution {

public:

int rearrangeSticks(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(k + 1));

for (int j = 1; j <= k; ++j) {

dp[j][j] = 1;

for (int i = j + 1; i <= n; ++i)

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod;

}

return dp[n][k];

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None)

def rearrangeSticks(self, n: int, k: int) -> int:

if k == 0: return 0

if k == n or n <= 2: return 1

return (self.rearrangeSticks(n - 1, k - 1) +

(n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7)