Posts published in “Dynamic Programming”

花花酱 LeetCode 1626. Best Team With No Conflicts

By zxi on October 18, 2020

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all the players in the team.

However, the basketball team is not allowed to have conflicts. A conflict exists if a younger player has a strictly higher score than an older player. A conflict does not occur between players of the same age.

Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the i^th player, respectively, return the highest overall score of all possible basketball teams.

Example 1:

Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.

Example 2:

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

Example 3:

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players.

Constraints:

1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 10⁶
1 <= ages[i] <= 1000

Solution: Sort + DP

Sort by (age, score) in descending order. For j < i, age[j] >= age[i]

dp[i] = max(dp[j] | score[j] >= score[i], j < i) + score[i]

Basically, we want to find the player j with best score among [0, i), and make sure score[i] <= score[j] (since age[j] >= age[i]) then we won’t have any conflicts.

ans = max(dp)

C++

// Author: Huahua

class Solution {

public:

int bestTeamScore(vector<int>& scores, vector<int>& ages) {

const int n = scores.size();

vector<pair<int, int>> players(n);

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

players[i] = {ages[i], scores[i]};

sort(rbegin(players), rend(players));

// dp[i] = max score of the first i players, i must be selected.

vector<int> dp(n);

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

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

if (players[i].second <= players[j].second)

dp[i] = max(dp[i], dp[j]);

dp[i] += players[i].second;

}

return *max_element(begin(dp), end(dp));

}

};

花花酱 LeetCode 1621. Number of Sets of K Non-Overlapping Line Segments

By zxi on October 17, 2020

Given n points on a 1-D plane, where the i^th point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10⁹ + 7.

Example 1:

Input: n = 4, k = 2
Output: 5
Explanation: 
The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10⁹ + 7 gives us 796297179.

Example 4:

Input: n = 5, k = 3
Output: 7

Example 5:

Input: n = 3, k = 2
Output: 1

Constraints:

2 <= n <= 1000
1 <= k <= n-1

Solution 1: Naive DP (TLE)

dp[n][k] := ans of problem(n, k)
dp[n][1] = n * (n – 1) / 2 # C(n,2)
dp[n][k] = 1 if k == n – 1
dp[n][k] = 0 if k >= n
dp[n][k] = sum((i – 1) * dp(n – i + 1, k – 1) 2 <= i < n

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

C++

class Solution {

public:

int numberOfSets(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> cache(n + 1, vector<int>(k + 1));

function<int(int, int)> dp = [&](int n, int k) {

if (k >= n) return 0;

if (k == 1) return n * (n - 1) / 2;

if (k == n - 1) return 1;

int& ans = cache[n][k];

if (ans) return ans;

for (long i = 2; i < n; ++i) {

const int t = ((i - 1) * dp(n - i + 1, k - 1)) % kMod;

ans = (ans + t) % kMod;

}

return ans;

};

return dp(n, k);

}

};

Solution 2: DP w/ Prefix Sum

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 940 ms

class Solution:

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

kMod = 10**9 + 7

dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(n + 1):

dp[i][0] = 1

for j in range(1, k + 1):

s = 0

for i in range(1, n + 1):

dp[i][j] = (s + dp[i - 1][j])

s += dp[i][j - 1]

return dp[n][k] % kMod

Solution 3: DP / 3D State

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 940 ms

class Solution:

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

kMod = 10**9 + 7

@lru_cache(None)

def dp(n: int, k: int, e: int) -> int:

if k == 0: return 1

if k > n: return 0

return (dp(n - 1, k, e) + dp(n + e - 1, k - e, 1 - e)) % kMod

return dp(n, k, 0)

Solution 4: DP / Mathematical induction

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 648 ms

class Solution:

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

@lru_cache(None)

def dp(n: int, k: int) -> int:

if k >= n: return 0

if k == 1: return n * (n - 1) // 2

if k == n - 1: return 1

return 2 * dp(n - 1, k) - dp(n - 2, k) + dp(n - 1, k - 1)

return dp(n, k) % (10**9 + 7)

Solution 5: DP / Reduction

This problem can be reduced to: given n + k – 1 points, pick k segments (2*k points).
if two consecutive points were selected by two segments e.g. i for A and i+1 for B, then they share a point in the original space.
Answer C(n + k – 1, 2*k)

Time complexity: O((n+k)*2) Pascal’s triangle
Space complexity: O((n+k)*2)

C++

class Solution {

public:

int numberOfSets(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> dp(n + k , vector<int>(n + k));

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

dp[i][0] = dp[i][i] = 1;

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

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

}

return dp[n + k - 1][2 * k];

}

};

花花酱 LeetCode 1595. Minimum Cost to Connect Two Groups of Points

By zxi on September 23, 2020

You are given two groups of points where the first group has size₁ points, the second group has size₂ points, and size₁ >= size₂.

The cost of the connection between any two points are given in an size₁ x size₂ matrix where cost[i][j] is the cost of connecting point i of the first group and point j of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.

Return the minimum cost it takes to connect the two groups.

Example 1:

Input: cost = [[15, 96], [36, 2]]
Output: 17
Explanation: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.

Example 2:

Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
Output: 4
Explanation: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.

Example 3:

Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
Output: 10

Constraints:

size₁ == cost.length
size₂ == cost[i].length
1 <= size₁, size₂ <= 12
size₁ >= size₂
0 <= cost[i][j] <= 100

Solution 1: Bistmask DP

dp[i][s] := min cost to connect first i (1-based) points in group1 and a set of points (represented by a bitmask s) in group2.

ans = dp[m][1 << n – 1]

dp[i][s | (1 << j)] := min(dp[i][s] + cost[i][j], dp[i-1][s] + cost[i][j])

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

C++/Bottom up

class Solution {

public:

int connectTwoGroups(vector<vector<int>>& cost) {

constexpr int kInf = 1e9;

const int m = cost.size();

const int n = cost[0].size();

// dp[i][s] := min cost to connect first i points in group1

// and points (bitmask s) in group2.

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

dp[0][0] = 0;

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

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

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

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

dp[i + 1][s] + cost[i][j],

dp[i][s] + cost[i][j]});

return dp[m].back();

}

};

花花酱 LeetCode 1594. Maximum Non Negative Product in a Matrix

By zxi on September 21, 2020

You are given a rows x cols matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (rows - 1, cols - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.

Return the maximum non-negative product modulo 10⁹ + 7. If the maximum product is negative return -1.

Notice that the modulo is performed after getting the maximum product.

Example 1:

Input: grid = [[-1,-2,-3],
               [-2,-3,-3],
               [-3,-3,-2]]
Output: -1
Explanation: It's not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.

Example 2:

Input: grid = [[1,-2,1],
               [1,-2,1],
               [3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is in bold (1 * 1 * -2 * -4 * 1 = 8).

Example 3:

Input: grid = [[1, 3],
               [0,-4]]
Output: 0
Explanation: Maximum non-negative product is in bold (1 * 0 * -4 = 0).

Example 4:

Input: grid = [[ 1, 4,4,0],
               [-2, 0,0,1],
               [ 1,-1,1,1]]
Output: 2
Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).

Constraints:

1 <= rows, cols <= 15
-4 <= grid[i][j] <= 4

Solution: DP

Use two dp arrays,

dp_max[i][j] := max product of matrix[0~i][0~j]
dp_min[i][j] := min product of matrix[0~i][0~j]

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

C++

// Author: Huahua

class Solution {

public:

int maxProductPath(vector<vector<int>>& grid) {

constexpr int kMod = 1e9 + 7;

const int m = grid.size();

const int n = grid[0].size();

vector<vector<long>> dp_max(m, vector<long>(n));

vector<vector<long>> dp_min(m, vector<long>(n));

dp_max[0][0] = dp_min[0][0] = grid[0][0];

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

dp_max[i][0] = dp_min[i][0] = dp_min[i - 1][0] * grid[i][0];

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

dp_max[0][j] = dp_min[0][j] = dp_min[0][j - 1] * grid[0][j];

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

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

if (grid[i][j] >= 0) {

dp_max[i][j] = max(dp_max[i - 1][j], dp_max[i][j - 1]) * grid[i][j];

dp_min[i][j] = min(dp_min[i - 1][j], dp_min[i][j - 1]) * grid[i][j];

} else {

dp_max[i][j] = min(dp_min[i - 1][j], dp_min[i][j - 1]) * grid[i][j];

dp_min[i][j] = max(dp_max[i - 1][j], dp_max[i][j - 1]) * grid[i][j];

}

return dp_max[m - 1][n - 1] >= 0 ? dp_max[m - 1][n - 1] % kMod : -1;

}

};

花花酱 LeetCode 1575. Count All Possible Routes

By zxi on September 5, 2020

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.

Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).

Return the count of all possible routes from start to finish.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
Output: 4
Explanation: The following are all possible routes, each uses 5 units of fuel:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:

Input: locations = [4,3,1], start = 1, finish = 0, fuel = 6
Output: 5
Explanation: The following are all possible routes:
1 -> 0, used fuel = 1
1 -> 2 -> 0, used fuel = 5
1 -> 2 -> 1 -> 0, used fuel = 5
1 -> 0 -> 1 -> 0, used fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0, used fuel = 5

Example 3:

Input: locations = [5,2,1], start = 0, finish = 2, fuel = 3
Output: 0
Explanation: It's impossible to get from 0 to 2 using only 3 units of fuel since the shortest route needs 4 units of fuel.

Example 4:

Input: locations = [2,1,5], start = 0, finish = 0, fuel = 3
Output: 2
Explanation: There are two possible routes, 0 and 0 -> 1 -> 0.

Example 5:

Input: locations = [1,2,3], start = 0, finish = 2, fuel = 40
Output: 615088286
Explanation: The total number of possible routes is 2615088300. Taking this number modulo 10^9 + 7 gives us 615088286.

Constraints:

2 <= locations.length <= 100
1 <= locations[i] <= 10^9
All integers in locations are distinct.
0 <= start, finish < locations.length
1 <= fuel <= 200

Solution: DP

dp[j][f] := # of ways to start from city ‘start’ to reach city ‘j’ with fuel level f.

dp[j][f] = sum(dp[i][f + d]) d = dist(i, j)

init: dp[start][fuel] = 1

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

C++

class Solution {

public:

int countRoutes(vector<int>& x, int start, int finish, int fuel) {

constexpr int kMod = 1e9 + 7;

const int n = x.size();

vector<vector<int>> dp(n, vector<int>(fuel + 1));

dp[start][fuel] = 1;

for (int f = fuel; f > 0; --f)

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

if (!dp[i][f] || abs(x[i] - x[finish]) > f) continue; // pruning.

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

const int d = abs(x[i] - x[j]);

if (i == j || f < d) continue;

dp[j][f - d] = (dp[j][f - d] + dp[i][f]) % kMod;

}

return accumulate(begin(dp[finish]), end(dp[finish]), 0LL) % kMod;

}

};

Python3

# Author: Huahua

class Solution:

def countRoutes(self, x: List[int], start: int, finish: int, fuel: int) -> int:

@lru_cache(None)

if f < 0: return 0

return (sum(dp(j, f - abs(x[i] - x[j]))

for j in range(len(x)) if i != j) + (i == finish)) % (10**9 + 7)

return dp(start, fuel)