Posts tagged as “dp”

花花酱 LeetCode 119. Pascal’s Triangle II

By zxi on November 27, 2021

Given an integer rowIndex, return the rowIndex^th (0-indexed) row of the Pascal’s triangle.

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

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Solution: Remember last row

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

C++

# Author: huahua

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<int> ans(1, 1);

for (int i = 2; i <= rowIndex + 1; ++i) {

vector<int> tmp(i, 1);

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

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

swap(ans, tmp);

}

return ans;

}

};

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

}

};

Posts tagged as “dp”

花花酱 LeetCode 119. Pascal’s Triangle II

Solution: Remember last row

C++

Related Problems

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