Posts tagged as “dp”

花花酱 LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary

By zxi on October 31, 2020

You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

target should be formed from left to right.
To form the i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].
Once you use the k^th character of the j^th string of words, you can no longer use the x^th character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

Example 3:

Input: words = ["abcd"], target = "abcd"
Output: 1

Example 4:

Input: words = ["abab","baba","abba","baab"], target = "abba"
Output: 16

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
All strings in words have the same length.
1 <= target.length <= 1000
words[i] and target contain only lowercase English letters.

Solution: DP

dp[i][j] := # of ways to form target[0~j] where the j-th letter is from the i-th column of words.
count[i][j] := # of words that have word[i] == target[j]

dp[i][j] = dp[i-1][j-1] * count[i][j]

Time complexity: O(mn)
Space complexity: O(mn) -> O(n)

C++

class Solution {

public:

int numWays(vector<string>& words, string target) {

constexpr int kMod = 1e9 + 7;

const int n = target.length();

const int m = words[0].length();

vector<long> dp(n); // dp[j] = # of ways to form t[0~j]

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

vector<int> count(26);

for (const string& word: words)

++count[word[i] - 'a'];

for (int j = min(i, n - 1); j >= 0; --j)

dp[j] = (dp[j] + (j > 0 ? dp[j - 1] : 1) *

count[target[j] - 'a']) % kMod;

}

return dp[n - 1];

}

};

花花酱 LeetCode 1631. Path With Minimum Effort

By zxi on October 24, 2020

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute differencein heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10⁶

Solution: “Lazy BFS / DP”

dp[y][x] = min(max(dp[ty][tx], abs(h[ty][tx] – h[y][x]))) (x, y) and (tx, ty) are neighbors
repeat this process for at most rows * cols times.
if dp does not change after one round which means we found the optimal solution and can break earlier.

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

C++

// Author: Huahua, 824 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const int r = heights.size();

const int c = heights[0].size();

int dp[100][100];

memset(dp, 0x7f, sizeof(dp));

dp[0][0] = 0;

vector<int> dirs{0, -1, 0, 1, 0};

for (int k = 0; k < r * c; ++k) {

bool stable = true;

for (int y = 0; y < r; ++y)

for (int x = 0; x < c; ++x)

for (int d = 0; d < 4; ++d) {

int tx = x + dirs[d];

int ty = y + dirs[d + 1];

if (tx < 0 || tx == c || ty < 0 || ty == r) continue;

int t = max(dp[ty][tx], abs(heights[ty][tx] - heights[y][x]));

if (t < dp[y][x]) {

stable = false;

dp[y][x] = t;

}

if (stable) break;

}

return dp[r - 1][c - 1];

}

};

Solution 2: Binary Search + BFS

Use binary search to guess a cost and then check whether there is path that is under the cost.

Time complexity: O(mn*log(max(h) – min(h)))
Space complexity: O(mn)

C++

// Author: Huahua, 620 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const int rows = heights.size();

const int cols = heights[0].size();

vector<int> dirs{0, -1, 0, 1, 0};

auto bfs = [&](int cost) -> bool {

queue<pair<int, int>> q;

vector<int> seen(cols * rows);

q.emplace(0, 0);

seen[0] = 1;

while (!q.empty()) {

auto [cx, cy] = q.front(); q.pop();

if (cx == cols - 1 && cy == rows - 1) return true;

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

int x = cx + dirs[i];

int y = cy + dirs[i + 1];

if (x < 0 || x == cols || y < 0 || y == rows) continue;

if (abs(heights[cy][cx] - heights[y][x]) > cost) continue;

if (seen[y * cols + x]++) continue;

q.emplace(x, y);

}

return false;

};

int l = 0, r = 1e6 + 1;

while (l < r) {

const int m = l + (r - l) / 2;

if (bfs(m)) {

r = m;

} else {

l = m + 1;

}

return l;

}

};

Solution 3: Dijkstra

Time complexity: O(mnlog(mn))
Space complexity: O(mn)

C++

// Author: Huahua, 216 ms

class Solution {

public:

int minimumEffortPath(vector<vector<int>>& heights) {

const vector<int> dirs{0, -1, 0, 1, 0};

const int rows = heights.size();

const int cols = heights[0].size();

using Node = pair<int, int>;

priority_queue<Node, vector<Node>, greater<Node>> q;

vector<int> dist(rows * cols, INT_MAX / 2);

q.emplace(0, 0);

dist[0] = 0;

while (!q.empty()) {

auto [t, u] = q.top(); q.pop();

if (u == rows * cols - 1) return t;

if (t > dist[u]) continue;

const int ux = u % cols;

const int uy = u / cols;

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

const int x = ux + dirs[i];

const int y = uy + dirs[i + 1];

if (x < 0 || x == cols || y < 0 || y == rows) continue;

const int v = y * cols + x;

const int c = abs(heights[uy][ux] - heights[y][x]);

if (max(t, c) >= dist[v]) continue;

q.emplace(dist[v] = max(t, c), v);

}

return -1;

}

};

花花酱 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();

}

};