Posts published in “Dynamic Programming”

花花酱 LeetCode 1493. Longest Subarray of 1’s After Deleting One Element

By zxi on June 27, 2020

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array.

Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Example 4:

Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Example 5:

Input: nums = [0,0,0]
Output: 0

Constraints:

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.

Solution 1: DP

Preprocess:
l[i] := longest 1s from left side ends with nums[i], l[i] = nums[i] + nums[i] * l[i – 1]
r[i] := longest 1s from right side ends with nums[i], r[i] = nums[i] + nums[i] * r[i + 1]

Use each node as a bridge (ignored), the total number of consecutive 1s = l[i – 1] + r[i + 1].

ans = max{l[i-1] + r[i +1]}
Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

vector<int> l(n);

vector<int> r(n);

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

l[i] = (i > 0 ? l[i - 1] * nums[i] : 0) + nums[i];

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

r[i] = (i < n - 1 ? r[i + 1] * nums[i] : 0) + nums[i];

int ans = 0;

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

ans = max(ans, (i > 0 ? l[i - 1] : 0) +

(i < n - 1 ? r[i + 1] : 0));

return ans;

}

};

Solution 2: DP

dp[i][0] := longest subarray ends with nums[i] has no ones.
dp[i][0] := longest subarray ends with nums[i] has 1 one.
if nums[i] == 1:
dp[i][0] = dp[i – 1][0] + 1
dp[i][1] = dp[i – 1][1] + 1
if nums[i] == 0:
dp[i][0] = 0
dp[i][1] = dp[i – 1][0] + 1
Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

// dp[i][0] := longest subarray ends with nums[i-1] has no zeros.

// dp[i][0] := longest subarray ends with nums[i-1] has 1 zero.

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

int ans = 0;

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

if (nums[i - 1] == 1) {

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

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

} else {

dp[i][0] = 0;

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

}

ans = max({ans, dp[i][0] - 1, dp[i][1] - 1});

}

return ans;

}

};

Solution 3: Sliding Window

Maintain a sliding window l ~ r s.t sum(num[l~r]) >= r – l. There can be at most one 0 in the window.
ans = max{r – l} for all valid windows.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

int sum = 0; // sum of nums[l~r].

for (int l = 0, r = 0; r < n; ++r) {

sum += nums[r];

// Maintain sum >= r - l, at most 1 zero.

while (l < r && sum < r - l)

sum -= nums[l++];

ans = max(ans, r - l);

}

return ans;

}

};

花花酱 LeetCode 1478. Allocate Mailboxes

By zxi on June 14, 2020

Given the array houses and an integer k. where houses[i] is the location of the ith house along a street, your task is to allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Example 3:

Input: houses = [7,4,6,1], k = 1
Output: 8

Example 4:

Input: houses = [3,6,14,10], k = 4
Output: 0

Constraints:

n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10^4
1 <= k <= n
Array houses contain unique integers.

Solution: DP

First, we need to sort the houses by their location.

This is a partitioning problem, e.g. optimal solution to partition first N houses into K groups. (allocating K mailboxes for the first N houses).

The key of this problem is to solve a base case, optimally allocating one mailbox for houses[i~j], The intuition is to put the mailbox in the middle location, this only works if there are only tow houses, or all the houses are evenly distributed. The correct location is the “median position” of a set of houses. For example, if the sorted locations are [1,2,3,100], the average will be 26 which costs 146 while the median is 2, and the cost becomes 100.

dp[i][k] := min cost to allocate k mailboxes houses[0~i].

base cases:

dp[i][1] = cost(0, i), min cost to allocate one mailbox.
dp[i][k] = 0 if k > i, more mailboxes than houses. // this is actually a pruning.

transition:

dp[i][k] = min(dp[p][k-1] + cost(p + 1, i)) 0 <= p < i,

allocate k-1 mailboxes for houses[0~p], and allocate one for houses[p+1~i]

ans:

dp[n-1][k]

Time complexity: O(n^3)
Space complexity: O(n^2) -> O(n)

C++

// Author: Huahua

class Solution {

public:

int minDistance(vector<int>& houses, int k) {

constexpr int kInf = 1e9;

const int n = houses.size();

sort(begin(houses), end(houses));

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

vector<vector<int>> costs(n + 1, vector<int>(n + 1, kInf));

// min cost to allocate one mailbox for houses[i~j].

auto cost = [&](int i, int j) {

int& ans = costs[i][j];

if (ans != kInf) return ans;

const int m = i + (j - i) / 2;

int box = 0;

if ((j - i + 1) & 1) // odd number of houses.

box = houses[m];

else // even number of houses.

box = (houses[m] + houses[m + 1]) / 2;

ans = 0;

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

ans += abs(houses[h] - box);

return ans;

};

// min cost to allocate k mailboxes for houses[0~i].

function<int(int, int)> solve = [&](int i, int k) {

if (k > i) return 0; // more mailboxs than houses.

if (k == 1) return cost(0, i);

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

if (ans != kInf) return ans;

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

ans = min(ans, solve(p, k - 1) + cost(p + 1, i));

return ans;

};

return solve(n - 1, k);

}

};

O(1) time to compute cost. O(n) Time and space for pre-processing.

C++

// Author: Huahua

vector<int> sums(n + 1);

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

sums[i] = sums[i - 1] + houses[i - 1];

// min cost to allocate one mailbox for houses[i~j].

auto cost = [&](int i, int j) {

const int m1 = (i + j) / 2;

const int m2 = (i + j + 1) / 2;

const int center = (houses[m1] + houses[m2]) / 2;

return (m1 - i + 1) * center - (sums[m1 + 1] - sums[i])

+ (sums[j + 1] - sums[m2]) - (j - m2 + 1) * center;

};

花花酱 LeetCode 1473. Paint House III

By zxi on June 7, 2020

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).

Given an array houses, an m * n matrix cost and an integer target where:

houses[i]: is the color of the house i, 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j+1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if not possible return -1.

Example 1:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:

Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

Constraints:

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

Solution: DP

dp[k][i][c] := min cost to form k neighbors with first i houses and i-th house is in color c.

dp[k][i][c] := min{dp[k-(c != cj)][j][cj] for cj in 1..n} + 0 if houses[i] == c else cost[i][c]

init: dp[0][0][*] = 0 otherwise inf
ans = min(dp[target][m])

Time complexity: O(T*M*N^2)
Space complexity: O(T*M*N) -> O(M*N)

C++

// Author: Huahua

// Author: Huahua， 104ms, 17.9MB

class Solution {

public:

int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {

constexpr int kInf = 1e9 + 7, s = 1;

// dp[k][i][c] := min cost to form k neighbors with first i houses and end with color c.

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

fill(begin(dp[0][0]), end(dp[0][0]), 0);

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

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

const int hi = houses[i - 1];

const int hj = i >= 2 ? houses[i - 2] : 0;

const auto& [si, ei] = hi ? tie(hi, hi) : tie(s, n);

const auto& [sj, ej] = hj ? tie(hj, hj) : tie(s, n);

for (int ci = si; ci <= ei; ++ci) {

const int v = ci == hi ? 0 : cost[i - 1][ci - 1];

for (int cj = sj; cj <= ej; ++cj)

dp[k][i][ci] = min(dp[k][i][ci], dp[k - (ci != cj)][i - 1][cj] + v);

}

const int ans = *min_element(begin(dp[target][m]), end(dp[target][m]));

return ans >= kInf ? -1 : ans;

}

};

花花酱 LeetCode 1463. Cherry Pickup II

By zxi on May 30, 2020

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
When both robots stay on the same cell, only one of them takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
Output: 22

Example 4:

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Solution: DP

dp[y][x1][x2] := max cherry when ro1 at (x1, y) and ro2 at (x2, y)
dp[y][x1][x2] = max(dp[y+1][x1 + dx1][x2 + dx2]) -1 <= dx1, dx2 <= 1

Time complexity: O(c^2*r)
Space complexity: O(c^2*r)

C++

// Author: Huahua

class Solution {

public:

int cherryPickup(vector<vector<int>>& grid) {

const int r = grid.size();

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

vector<vector<vector<int>>> cache(r, vector<vector<int>>(c, vector<int>(c, -1)));

function<int(int, int, int)> dp = [&](int y, int x1, int x2) {

if (x1 < 0 || x1 >= c || x2 < 0 || x2 >= c || y < 0 || y >= r) return 0;

int& ans = cache[y][x1][x2];

if (ans != -1) return ans;

const int cur = grid[y][x1] + (x1 != x2) * grid[y][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp(y + 1, x1 + d1, x2 + d2));

return ans;

};

return dp(0, 0, c - 1);

}

};

Bottom-up

C++

// Author: Huahua

class Solution {

public:

int cherryPickup(vector<vector<int>>& grid) {

const int r = grid.size();

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

vector<vector<vector<int>>> dp(r + 2,

vector<vector<int>>(c + 2, vector<int>(c + 2)));

for (int y = r; y >= 1; --y)

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

int& ans = dp[y][x1][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp[y + 1][x1 + d1][x2 + d2]);

}

return dp[1][1][c];

}

};

O(c^2) Space

C++

// Author: Huahua

class Solution {

public:

int cherryPickup(vector<vector<int>>& grid) {

const int r = grid.size();

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

vector<vector<int>> dp(c + 2, vector<int>(c + 2));

for (int y = r; y >= 1; --y) {

vector<vector<int>> tmp(c + 2, vector<int>(c + 2));

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

tmp[x1][x2] = max(tmp[x1][x2], cur + dp[x1 + d1][x2 + d2]);

}

dp.swap(tmp);

}

return dp[1][c];

}

};

花花酱 LeetCode 1458. Max Dot Product of Two Subsequences

By zxi on May 24, 2020

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:

1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

Solution: DP

dp[i][j] := max product of nums1[0~i], nums2[0~j].

dp[i][j] = max(dp[i-1][j], dp[i][j -1], max(0, dp[i-1][j-1]) + nums1[i]*nums2[j])

Time complexity: O(n1*n2)
Space complexity: O(n1*n2)

C++

// Author: Huahua

class Solution {

public:

int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// dp[i][j] = max dot product of two subsequences

// of nums1[0:i] and nums2[0:j]

vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN / 2));

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

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

dp[i][j] = max({

dp[i - 1][j],

dp[i][j - 1],

max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1]

});

return dp[n1][n2];

}

};

C++

// Author: Huahua

class Solution {

public:

int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// dp[i][j] = max dot product of two subsequences

// of nums1[0~i] and nums2[0~j]

vector<vector<int>> dp(n1, vector<int>(n2));

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

for (int j = 0; j < n2; ++j) {

dp[i][j] = nums1[i] * nums2[j];

if (i > 0 && j > 0) dp[i][j] += max(0, dp[i - 1][j - 1]);

if (i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j]);

if (j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1]);

}

return dp.back().back();

}

};