Posts tagged as “dp”

花花酱 LeetCode 2218. Maximum Value of K Coins From Piles

By zxi on March 28, 2022

There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.

In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.

Given a list piles, where piles[i] is a list of integers denoting the composition of the i^th pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

Example 1:

Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.

Example 2:

Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.

Constraints:

n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 10⁵
1 <= k <= sum(piles[i].length) <= 2000

Solution: DP

let dp(i, k) be the maximum value of picking k elements using piles[i:n].

dp(i, k) = max(dp(i + 1, k), sum(piles[i][0~j]) + dp(i + 1, k – j – 1)), 0 <= j < len(piles[i])

Time complexity: O(n * m), m = sum(piles[i]) <= 2000
Space complexity: O(n * k)

Python

# Author: Huahua

class Solution:

def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:

n = len(piles)

@cache

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

"""Max value of picking k elements using piles[i:n]."""

if i == n: return 0

ans, cur = dp(i + 1, k), 0

for j in range(min(len(piles[i]), k)):

ans = max(ans, (cur := cur + piles[i][j]) + dp(i + 1, k - j - 1))

return ans

return dp(0, k)

花花酱 LeetCode 2188. Minimum Time to Finish the Race

By zxi on February 28, 2022

You are given a 0-indexed 2D integer array tires where tires[i] = [f_i, r_i] indicates that the i^th tire can finish its x^th successive lap in f_i * r_i^(x-1) seconds.

For example, if f_i = 3 and r_i = 2, then the tire would finish its 1^st lap in 3 seconds, its 2^nd lap in 3 * 2 = 6 seconds, its 3^rd lap in 3 * 2² = 12 seconds, etc.

You are also given an integer changeTime and an integer numLaps.

The race consists of numLaps laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait changeTime seconds.

Return the minimum time to finish the race.

Example 1:

Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Explanation: 
Lap 1: Start with tire 0 and finish the lap in 2 seconds.
Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the race is 21 seconds.

Example 2:

Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Explanation: 
Lap 1: Start with tire 1 and finish the lap in 2 seconds.
Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the race is 25 seconds.

Constraints:

1 <= tires.length <= 10⁵
tires[i].length == 2
1 <= f_i, changeTime <= 10⁵
2 <= r_i <= 10⁵
1 <= numLaps <= 1000

Solution: DP

Observation: since ri >= 2, we must change tire within 20 laps, otherwise it will be slower.

pre-compute the time to finish k laps using each type of tire (k < 20), find min for each lap.

dp[i] = best[i], i < 20,
dp[i] = min{dp[i – j] + changeTime + best[j]}, i > 20

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

C++

// Author: Huahua

class Solution {

public:

int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {

constexpr int kMax = 20;

vector<long> best(kMax, INT_MAX);

for (const auto& t : tires)

for (long i = 1, l = t[0], s = t[0]; i < kMax && l < t[0] + changeTime; ++i, l *= t[1], s += l)

best[i] = min(best[i], s);

vector<long> dp(numLaps + 1, INT_MAX);

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

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

dp[i] = min(dp[i], best[j] + (i > j) * (changeTime + dp[i - j]));

return dp[numLaps];

}

};

花花酱 LeetCode 2140. Solving Questions With Brainpower

By zxi on January 30, 2022

You are given a 0-indexed 2D integer array questions where questions[i] = [points_i, brainpower_i].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you points_i points but you will be unable to solve each of the next brainpower_i questions. If you skip question i, you get to make the decision on the next question.

For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
- If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
- If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

Constraints:

1 <= questions.length <= 10⁵
questions[i].length == 2
1 <= points_i, brainpower_i <= 10⁵

Solution: DP

A more general version of 花花酱 LeetCode 198. House Robber

dp[i] := max points by solving questions[i:n].
dp[i] = max(dp[i + b + 1] + points[i] /* solve */ , dp[i+1] /* skip */)

ans = dp[0]

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

Python3

# Author: Huahua

class Solution:

def mostPoints(self, questions: List[List[int]]) -> int:

n = len(questions)

@cache

def dp(i: int) -> int:

if i >= n: return 0

p, b = questions[i]

return max(p + dp(i + b + 1), dp(i + 1))

return dp(0)

花花酱 LeetCode 2110. Number of Smooth Descent Periods of a Stock

By zxi on December 20, 2021

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the i^th day.

A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.

Return the number of smooth descent periods.

Example 1:

Input: prices = [3,2,1,4]
Output: 7
Explanation: There are 7 smooth descent periods:
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Note that a period with one day is a smooth descent period by the definition.

Example 2:

Input: prices = [8,6,7,7]
Output: 4
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3:

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Constraints:

1 <= prices.length <= 10⁵
1 <= prices[i] <= 10⁵

Solution: DP

Same as longest decreasing subarray.

dp[i] := length of longest smoothing subarray ends with nums[i].

dp[i] = dp[i – 1] + 1 if nums[i] + 1 = nums[i – 1] else 1

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

C++

// Author: Huahua

class Solution {

public:

long long getDescentPeriods(vector<int>& prices) {

const int n = prices.size();

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

long long ans = 1;

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

if (prices[i] - prices[i - 1] == -1)

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

ans += dp[i];

}

return ans;

}

};

花花酱 LeetCode Ultimate DP Study Plan Day 10

By zxi on December 11, 2021

413. Arithmetic Slices

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def numberOfArithmeticSlices(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

"""Number of arithmetic subarrays end with nums[i]."""

if i < 2: return 0

if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:

return 1 + dp(i - 1)

return 0

return sum(dp(i) for i in range(len(nums)))

91. Decode Ways

Python3

# Author: Huahua

# Time complexity: O(n^2) -> O(n)

# Space complexity: O(n)

class Solution:

@cache

def numDecodings(self, s: str) -> int:

if not s: return 1

if s[0] == '0': return 0

ans = self.numDecodings(s[1:])

if len(s) > 1 and (s[0] == '1' or (s[0] == '2' and s[1] <= '6')):

ans += self.numDecodings(s[2:])

return ans