Posts tagged as “dp”

花花酱 LeetCode 1510. Stone Game IV

By zxi on July 17, 2020

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5

Solution: Recursion w/ Memoization / DP

Let win(n) denotes whether the current play will win or not.
Try all possible square numbers and see whether the other player will lose or not.
win(n) = any(win(n – i*i) == False) ? True : False
base case: win(0) = False

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

C++

class Solution {

public:

bool winnerSquareGame(int n) {

vector<int> cache(n + 1, 0); // 0:Unknown, 1:Win, -1:Lose

function<int(int)> win = [&](int n) -> int {

if (n == 0) return -1;

if (cache[n]) return cache[n];

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

if (win(n - i * i) < 0) return cache[n] = 1;

return cache[n] = -1;

};

return win(n) > 0;

}

};

Java

class Solution {

private int[] cache;

public boolean winnerSquareGame(int n) {

this.cache = new int[n + 1];

return this.win(n) > 0;

}

private int win(int n) {

if (n == 0) return -1;

if (this.cache[n] != 0) return this.cache[n];

for (int i = (int)Math.sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0)

return this.cache[n] = 1;

return this.cache[n] = -1;

}

Python3

class Solution:

def winnerSquareGame(self, n: int) -> bool:

dp = [None] * (n + 1)

dp[0] = False

for i in range(0, n):

if dp[i]: continue

for j in range(1, n + 1):

if i + j * j > n: break

dp[i + j * j] = True

return dp[n]

花花酱 LeetCode 1504. Count Submatrices With All Ones

By zxi on July 5, 2020

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat = [[1,0,1],
              [1,1,0],
              [1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2:

Input: mat = [[0,1,1,0],
              [0,1,1,1],
              [1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Example 3:

Input: mat = [[1,1,1,1,1,1]]
Output: 21

Example 4:

Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5

Constraints:

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

Solution 1: Brute Force w/ Pruning

Time complexity: O(m^2*n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numSubmat(vector<vector<int>>& mat) {

const int R = mat.size();

const int C = mat[0].size();

// # of sub matrices with top-left at (sr, sc)

auto subMats = [&](int sr, int sc) {

int max_c = C;

int count = 0;

for (int r = sr; r < R; ++r)

for (int c = sc; c < max_c; ++c)

if (mat[r][c]) {

++count;

} else {

max_c = c;

}

return count;

};

int ans = 0;

for (int r = 0; r < R; ++r)

for (int c = 0; c < C; ++c)

ans += subMats(r, c);

return ans;

}

};

花花酱 LeetCode 1494. Parallel Courses II

By zxi on June 27, 2020

Given the integer n representing the number of courses at some university labeled from 1 to n, and the array dependencies where dependencies[i] = [x_i, y_i] represents a prerequisite relationship, that is, the course x_i must be taken before the course y_i. Also, you are given the integer k.

In one semester you can take at most k courses as long as you have taken all the prerequisites for the courses you are taking.

Return the minimum number of semesters to take all courses. It is guaranteed that you can take all courses in some way.

Example 1:

Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3 
Explanation: The figure above represents the given graph. In this case we can take courses 2 and 3 in the first semester, then take course 1 in the second semester and finally take course 4 in the third semester.

Example 2:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 
Explanation: The figure above represents the given graph. In this case one optimal way to take all courses is: take courses 2 and 3 in the first semester and take course 4 in the second semester, then take course 1 in the third semester and finally take course 5 in the fourth semester.

Example 3:

Input: n = 11, dependencies = [], k = 2
Output: 6

Constraints:

1 <= n <= 15
1 <= k <= n
0 <= dependencies.length <= n * (n-1) / 2
dependencies[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
All prerequisite relationships are distinct, that is, dependencies[i] != dependencies[j].
The given graph is a directed acyclic graph.

Solution: DP / Bitmask

NOTE: This is a NP problem, any polynomial-time algorithm is incorrect otherwise P = NP.

Variant 1:
dp[m] := whether state m is reachable, where m is the bitmask of courses studied.
For each semester, we enumerate all possible states from 0 to 2^n – 1, if that state is reachable, then we choose c (c <= k) courses from n and check whether we can study those courses.
If we can study those courses, we have a new reachable state, we set dp[m | courses] = true.

Time complexity: O(n*2^n*2^n) = O(n*n^4) <– This will be much smaller in practice.
and can be reduced to O(n*3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 52 ms, 14.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp(i)[s] := reachable(s) at semester i.

vector<int> dp(S);

dp[0] = 1;

for (int d = 1; d <= n; ++d) { // at most n semesters.

vector<int> tmp(S); // start a new semesters.

for (int s = 0; s < S; ++s) {

if (!dp[s]) continue; // not a reachable state.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

tmp[s | mask] = 1;

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k) {

tmp[s | c] = 1;

}

if (tmp.back()) return d;

}

dp.swap(tmp);

}

return -1;

}

};

Variant 2:
dp[m] := min semesters to reach state m.
dp[m | c] = min{dp[m | c], dp[m] + 1}, if we can reach m | c from m.
This allows us to get rid of enumerate n semesters.
Time complexity: O(2^n*2^n) <– This will be much smaller in practice.
and can be reduced to O(3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 16 ms, 8.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int kInf = 1e9;

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp[m] := min semesters to reach state m.

vector<int> dp(S, kInf);

dp[0] = 0;

for (int s = 0; s < S; ++s) {

if (dp[s] == kInf) continue; // not reachable.

// Generate a mask of courses we can study under state s.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

dp[s | mask] = min(dp[s | mask], dp[s] + 1);

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k)

dp[s | c] = min(dp[s | c], dp[s] + 1);

}

// Early termination?

if (dp.back() != kInf) return dp.back();

}

return dp.back();

}

};

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

};