Posts tagged as “dp”

花花酱 LeetCode 118. Pascal’s Triangle

By zxi on November 27, 2021

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> ans(numRows);

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

ans[i].resize(i + 1);

ans[i][0] = ans[i][i] = 1;

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

ans[i][j] = ans[i-1][j] + ans[i-1][j-1];

}

return ans;

}

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

By zxi on November 27, 2021

A farmer has a rectangular grid of land with m rows and n columns that can be divided into unit cells. Each cell is either fertile (represented by a 1) or barren (represented by a 0). All cells outside the grid are considered barren.

A pyramidal plot of land can be defined as a set of cells with the following criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of a pyramid is the topmost cell of the pyramid. The height of a pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r <= i <= r + h - 1 and c - (i - r) <= j <= c + (i - r).

An inverse pyramidal plot of land can be defined as a set of cells with similar criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of an inverse pyramid is the bottommost cell of the inverse pyramid. The height of an inverse pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r - h + 1 <= i <= r and c - (r - i) <= j <= c + (r - i).

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.

Given a 0-indexed m x n binary matrix grid representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in grid.

Example 1:

Input: grid = [[0,1,1,0],[1,1,1,1]]
Output: 2
Explanation:
The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid. 
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.

Example 2:

Input: grid = [[1,1,1],[1,1,1]]
Output: 2
Explanation:
The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. 
Hence the total number of plots is 1 + 1 = 2.

Example 3:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 0
Explanation:
There are no pyramidal or inverse pyramidal plots in the grid.

Example 4:

Input: grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
Output: 13
Explanation:
There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[i][j] is either 0 or 1.

Solution: DP

Let dp[i][j] be the height+1 of a Pyramid tops at i, j
dp[i][j] = min(dp[i+d][j – 1], dp[i + d][j + 1]) + 1 if dp[i-1][j] else grid[i][j]

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

Python

# Author: Huahua

class Solution:

def countPyramids(self, grid: List[List[int]]) -> int:

m = len(grid)

n = len(grid[0])

ans = 0

@cache

def dp(i: int, j: int, d: int) -> int:

if grid[i][j] and 0 <= i + d < m and 0 < j < n - 1 and grid[i + d][j]:

return min(dp(i + d, j - 1, d), dp(i + d, j + 1, d)) + 1

return grid[i][j]

for i, j in product(range(m), range(n)):

ans += max(0, dp(i, j, 1) - 1)

ans += max(0, dp(i, j, -1) - 1)

return ans

花花酱 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 1896. Minimum Cost to Change the Final Value of Expression

By zxi on August 9, 2021

You are given a valid boolean expression as a string expression consisting of the characters '1','0','&' (bitwise AND operator),'|' (bitwise OR operator),'(', and ')'.

For example, "()1|1" and "(1)&()" are not valid while "1", "(((1))|(0))", and "1|(0&(1))" are valid expressions.

Return the minimum cost to change the final value of the expression.

For example, if expression = "1|1|(0&0)&1", its value is 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1. We want to apply operations so that the new expression evaluates to 0.

The cost of changing the final value of an expression is the number of operations performed on the expression. The types of operations are described as follows:

Turn a '1' into a '0'.
Turn a '0' into a '1'.
Turn a '&' into a '|'.
Turn a '|' into a '&'.

Note: '&' does not take precedence over '|' in the order of calculation. Evaluate parentheses first, then in left-to-right order.

Example 1:

Input: expression = "1&(0|1)"
Output: 1
Explanation: We can turn "1&(0|1)" into "1&(0&1)" by changing the '|' to a '&' using 1 operation.
The new expression evaluates to 0.

Example 2:

Input: expression = "(0&0)&(0&0&0)"

Output: 3

Explanation: We can turn "(0&0)&(0&0&0)" into "(0|1)|(0&0&0)" using 3 operations.

The new expression evaluates to 1.

Example 3:

Input: expression = "(0|(1|0&1))"
Output: 1
Explanation: We can turn "(0|(1|0&1))" into "(0|(0|0&1))" using 1 operation.
The new expression evaluates to 0.

Constraints:

1 <= expression.length <= 10⁵
expression only contains '1','0','&','|','(', and ')'
All parentheses are properly matched.
There will be no empty parentheses (i.e: "()" is not a substring of expression).

Solution: DP, Recursion / Simulation w/ Stack

For each expression, stores the min cost to change value to 0 and 1.

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

C++

class Solution {

public:

int minOperationsToFlip(string expression) {

stack<array<int, 3>> s;

s.push({0, 0, 0});

for (char e : expression) {

if (e == '(')

s.push({0, 0, 0});

else if (e == '&' || e == '|')

s.top()[2] = e;

else {

if (isdigit(e)) s.push({e != '0', e != '1', 0});

auto [r0, r1, _] = s.top(); s.pop();

auto [l0, l1, op] = s.top(); s.pop();

if (op == '&') {

s.push({min(l0, r0),

min(l1 + r1, min(l1, r1) + 1),

0});

} else if (op == '|') {

s.push({min(l0 + r0, min(l0, r0) + 1),

min(l1, r1),

0});

} else {

s.push({r0, r1, 0});

}

return max(s.top()[0], s.top()[1]);

}

};

花花酱 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

Posts tagged as “dp”

花花酱 LeetCode 118. Pascal’s Triangle

Solution: Simulation

C++

Related Problems

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

Solution: DP

Python

花花酱 LeetCode 2008. Maximum Earnings From Taxi

Solution: DP

C++

花花酱 LeetCode 1896. Minimum Cost to Change the Final Value of Expression

Solution: DP, Recursion / Simulation w/ Stack

C++

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

Solution: DP

C++

Python3