Posts published in “Dynamic Programming”

花花酱 LeetCode 1770. Maximum Score from Performing Multiplication Operations

By zxi on February 21, 2021

You are given two integer arrays nums and multipliersof size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the i^th operation (1-indexed), you will:

Choose one integer x from either the start or the end of the array nums.
Add multipliers[i] * x to your score.
Remove x from the array nums.

Return the maximum score after performing m operations.

Example 1:

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

Example 2:

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

Constraints:

n == nums.length
m == multipliers.length
1 <= m <= 10³
m <= n <= 10⁵
-1000 <= nums[i], multipliers[i] <= 1000

Solution: DP

dp(i, j) := max score we can get with nums[i~j] left.

k = n – (j – i + 1)
dp(i, j) = max(dp(i + 1, j) + nums[i] * multipliers[k], dp(i, j-1) + nums[j] * multipliers[k])

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

C++/Top-Down

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, vector<int>& multipliers) {

const int m = multipliers.size();

const int n = nums.size();

vector<vector<int>> cache(m, vector<int>(m, INT_MIN));

function<int(int, int)> dp = [&](int i, int j) {

const int k = n - (j - i + 1);

if (k == m) return 0;

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

if (ans != INT_MIN) return ans;

return ans = max(dp(i + 1, j) + nums[i] * multipliers[k],

dp(i, j - 1) + nums[j] * multipliers[k]);

};

return dp(0, n - 1);

}

};

C++/Bottom-UP

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, vector<int>& multipliers) {

const int m = multipliers.size();

const int n = nums.size();

// dp[i][j] := max score of using first i elements and last j elements

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

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

for (int i = 0, j = k - i; i <= k; ++i, --j)

dp[i][j] = max((i ? dp[i - 1][j] + nums[i - 1] * multipliers[k - 1] : INT_MIN),

(j ? dp[i][j - 1] + nums[n - j] * multipliers[k - 1] : INT_MIN));

int ans = INT_MIN;

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

ans = max(ans, dp[i][m - i]);

return ans;

}

};

花花酱 LeetCode 1769. Minimum Number of Operations to Move All Balls to Each Box

By zxi on February 20, 2021

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the i^th box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the i^th box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Constraints:

n == boxes.length
1 <= n <= 2000
boxes[i] is either '0' or '1'

Solution: Prefix Sum + DP

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

C++

// Author: Huahua

class Solution {

public:

vector<int> minOperations(string boxes) {

const int n = boxes.size();

vector<int> ans(n);

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

ans[i] += c;

c += (s += boxes[i] - '0');

}

for (int i = n - 1, c = 0, s = 0; i >= 0; --i) {

ans[i] += c;

c += (s += boxes[i] - '0');

}

return ans;

}

};

花花酱 LeetCode 1751. Maximum Number of Events That Can Be Attended II

By zxi on February 6, 2021

You are given an array of events where events[i] = [startDay_i, endDay_i, value_i]. The i^th event starts at startDay_iand ends at endDay_i, and if you attend this event, you will receive a value of value_i. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints:

1 <= k <= events.length
1 <= k * events.length <= 10⁶
1 <= startDay_i <= endDay_i <= 10⁹
1 <= value_i <= 10⁶

Solution: DP + Binary Search

Sort events by ending time.
dp[i][j] := max value we can get by attending at most j events among events[0~i].
dp[i][j] = max(dp[i – 1][j], dp[p][j – 1] + value[i])
p is the first event that does not overlap with the current one.

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

C++

// Author: Huahua

class Solution {

public:

int maxValue(vector<vector<int>>& events, int k) {

const int n = events.size();

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

vector<int> e(n);

auto comp = [](const vector<int>& a, const vector<int>& b) {

return a[1] < b[1];

};

sort(begin(events), end(events), comp);

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

const int p = lower_bound(begin(events),

begin(events) + i,

vector<int>{0, events[i - 1][0], 0},

comp) - begin(events);

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

dp[i][j] = max(dp[i - 1][j],

dp[p][j - 1] + events[i - 1][2]);

}

return dp[n][k];

}

};

花花酱 LeetCode 1745. Palindrome Partitioning IV

By zxi on January 30, 2021

Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.

A string is said to be palindrome if it the same string when reversed.

Example 1:

Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.

Example 2:

Input: s = "bcbddxy"
Output: false
Explanation: s cannot be split into 3 palindromes.

Constraints:

3 <= s.length <= 2000
s consists only of lowercase English letters.

Solution: DP

dp[i][j] := whether s[i]~s[j] is a palindrome.

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

ans = any(dp[0][i-1] and dp[i][j] and dp[j][n-1]) for j in range(i, n – 1) for i in range(1, n)

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

C++

// Author: Huahua

class Solution {

public:

bool checkPartitioning(string s) {

const int n = s.length();

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

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j)

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

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

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

if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])

return true;

return false;

}

};

花花酱 LeetCode 1738. Find Kth Largest XOR Coordinate Value

By zxi on January 23, 2021

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.

The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).

Find the k^th largest value (1-indexed) of all the coordinates of matrix.

Example 1:

Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2:

Input: matrix = [[5,2],[1,6]], k = 2
Output: 5
Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3:

Input: matrix = [[5,2],[1,6]], k = 3
Output: 4
Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 10⁶
1 <= k <= m * n

Solution: DP

xor[i][j] = matrix[i][j] ^ xor[i – 1][j – 1] ^ xor[i – 1][j] ^ xor[i][j- 1]

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

C++

// Author: Huahua

class Solution {

public:

int kthLargestValue(vector<vector<int>>& matrix, int k) {

const int m = matrix.size(), n = matrix[0].size();

vector<int> v;

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

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

v.push_back(matrix[i][j]

^= (i ? matrix[i - 1][j] : 0)

^ (j ? matrix[i][j - 1] : 0)

^ (i * j ? matrix[i - 1][j - 1] : 0));

nth_element(begin(v), begin(v) + k - 1, end(v), greater<int>());

return v[k - 1];

}

};