Posts tagged as “dp”

花花酱 LeetCode 1671. Minimum Number of Removals to Make Mountain Array

By zxi on November 28, 2020

You may recall that an array arr is a mountain array if and only if:

arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums, return the minimum number of elements to remove to make numsa mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Example 3:

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4

Example 4:

Input: nums = [1,2,3,4,4,3,2,1]
Output: 1

Constraints:

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁹
It is guaranteed that you can make a mountain array out of nums.

Solution: DP / LIS

LIS[i] := longest increasing subsequence ends with nums[i]
LDS[i] := longest decreasing subsequence starts with nums[i]
Let nums[i] be the peak, the length of the mountain array is LIS[i] + LDS[i] – 1
Note: LIS[i] and LDS[i] must be > 1 to form a valid mountain array.
ans = min(n – (LIS[i] + LDS[i] – 1)) 0 <= i < n

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

C++

// Author: Huahua

class Solution {

public:

int minimumMountainRemovals(vector<int>& nums) {

const int n = nums.size();

vector<int> LIS(n, 1); // LIS[i] := Longest increasing subseq ends with nums[i]

vector<int> LDS(n, 1); // LDS[i] := Longest decreasing subseq starts with nums[i]

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

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

if (nums[i] > nums[j]) LIS[i] = max(LIS[i], LIS[j] + 1);

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

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

if (nums[i] > nums[j]) LDS[i] = max(LDS[i], LDS[j] + 1);

int ans = INT_MAX;

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

if (LIS[i] < 2 || LDS[i] < 2) continue;

ans = min(ans, n - (LIS[i] + LDS[i] - 1));

}

return ans;

}

};

花花酱 LeetCode 1659. Maximize Grid Happiness

By zxi on November 22, 2020

You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid, and there are two types of people: introverts and extroverts. There are introvertsCount introverts and extrovertsCount extroverts.

You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you do not have to have all the people living in the grid.

The happiness of each person is calculated as follows:

Introverts start with 120 happiness and lose 30 happiness for each neighbor (introvert or extrovert).
Extroverts start with 40 happiness and gain 20 happiness for each neighbor (introvert or extrovert).

Neighbors live in the directly adjacent cells north, east, south, and west of a person’s cell.

The grid happiness is the sum of each person’s happiness. Return the maximum possible grid happiness.

Example 1:

Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
Output: 240
Explanation: Assume the grid is 1-indexed with coordinates (row, column).
We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).
- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120
- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
The grid happiness is 120 + 60 + 60 = 240.
The above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.

Example 2:

Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
Output: 260
Explanation: Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).
- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80
- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
The grid happiness is 90 + 80 + 90 = 260.

Example 3:

Input: m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
Output: 240

Constraints:

1 <= m, n <= 5
0 <= introvertsCount, extrovertsCount <= min(m * n, 6)

Solution: DP

dp(x, y, in, ex, mask) := max score at (x, y) with in and ex left and the state of previous row is mask.

Mask is ternary, mask(i) = {0, 1, 2} means {empty, in, ex}, there are at most 3^n = 3^5 = 243 different states.

Total states / Space complexity: O(m*n*3^n*in*ex) = 5*5*3^5*6*6
Space complexity: O(m*n*3^n*in*ex)

C++

class Solution {

public:

int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {

constexpr int kMaxStates = 243;

int dp[6][6][7][7][kMaxStates];

memset(dp, -1, sizeof(dp));

auto get = [](int val, int i) { return val / static_cast<int>(pow(3, i)) % 3; };

auto update = [](int val, int s) { return (val * 3 + s) % kMaxStates; };

vector<int> init{0, 120, 40};

vector<int> gain{0, -30, 20};

function<int(int,int,int,int,int)> dfs = [&](int x, int y, int in, int ex, int mask) {

if (in == 0 && ex == 0) return 0; // Nothing left.

if (x == n) { x = 0; ++y; }

if (y == m) return 0; // Done.

int& ans = dp[x][y][in][ex][mask];

if (ans != -1) return ans;

ans = dfs(x + 1, y, in, ex, update(mask, 0)); // Skip current cell.

vector<int> counts{0, in, ex};

int up = get(mask, n - 1);

int left = get(mask, 0);

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

if (counts[i] == 0) continue;

int s = init[i];

if (y - 1 >= 0 && up) s += gain[i] + gain[up];

if (x - 1 >= 0 && left) s += gain[i] + gain[left];

ans = max(ans, s + dfs(x + 1, y, in - (i==1), ex - (i==2), update(mask, i)));

}

return ans;

};

return dfs(0, 0, introvertsCount, extrovertsCount, 0);

}

};

Python3

# Author: Huahua

class Solution:

def getMaxGridHappiness(self, m: int, n: int, I: int, E: int) -> int:

init, gain = [None, 120, 40], [None, -30, 20]

get = lambda val, i: (val // (3 ** i)) % 3

update = lambda val, s: (val * 3 + s) % (3 ** n)

@lru_cache(None)

def dp(x: int, y: int, i: int, e: int, mask: int) -> int:

if x == n: x, y = 0, y + 1

if i + e == 0 or y == m: return 0

ans = dp(x + 1, y, i, e, update(mask, 0))

up, left = get(mask, n - 1), get(mask, 0)

for cur, count in enumerate([i, e], 1):

if count == 0: continue

s = init[cur]

if x - 1 >= 0 and left: s += gain[cur] + gain[left]

if y - 1 >= 0 and up: s += gain[cur] + gain[up]

ans = max(ans, s + dp(x + 1, y,

i - (cur == 1),

e - (cur == 2),

update(mask, cur)))

return ans

return dp(0, 0, I, E, 0)

花花酱 LeetCode 1655. Distribute Repeating Integers

By zxi on November 14, 2020

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the i^th customer ordered. Determine if it is possible to distribute nums such that:

The i^th customer gets exactly quantity[i] integers,
The integers the i^th customer gets are all equal, and
Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10⁵
There are at most 50 unique values in nums.

Solution1: Backtracking

Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)

C++

// Author: Huahua

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

unordered_map<int, int> m;

for (int x : nums) ++m[x];

vector<int> cnt;

for (const auto& [x, c] : m) cnt.push_back(c);

const int q = quantity.size();

const int n = cnt.size();

function<bool(int)> dfs = [&](int d) {

if (d == q) return true;

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

if (cnt[i] >= quantity[d]) {

cnt[i] -= quantity[d];

if (dfs(d + 1)) return true;

cnt[i] += quantity[d];

}

return false;

};

sort(rbegin(cnt), rend(cnt));

sort(rbegin(quantity), rend(quantity));

return dfs(0);

}

};

Solution 2: Bitmask + all subsets

dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.

Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

function<bool(int, int)> dp = [&](int mask, int i) -> bool {

if (mask == 0) return true;

if (i == n) return false;

auto& ans = cache[mask][i];

if (ans.has_value()) return ans.value();

int cur = mask;

while (cur) {

if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) {

ans = true;

return true;

}

cur = (cur - 1) & mask;

}

ans = dp(mask, i + 1);

return ans.value();

};

return dp((1 << m) - 1, 0);

}

};

Python3

# Author: Huahua

class Solution:

def canDistribute(self, nums: List[int],

quantity: List[int]) -> bool:

cnts = list(Counter(nums).values())

m = len(quantity)

n = len(cnts)

sums = [0] * (1 << m)

for mask in range(1 << m):

for i in range(m):

if mask & (1 << i): sums[mask] += quantity[i]

@lru_cache(None)

def dp(mask: int, i: int) -> bool:

if not mask: return True

if i < 0: return False

cur = mask

while cur:

if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):

return True

cur = (cur - 1) & mask

return dp(mask, i - 1)

return dp((1 << m) - 1, n - 1)

Bottom up:

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

// dp[mask][i] := use first i types to satisfy mask customers.

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

dp[0][0] = 1;

for (int mask = 0; mask < 1 << m; ++mask)

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

dp[mask][i + 1] |= dp[mask][i];

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

if (sums[cur] <= cnt[i] && dp[mask ^ cur][i])

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

}

return dp[(1 << m) - 1][n];

}

};

花花酱 LeetCode 1653. Minimum Deletions to Make String Balanced

By zxi on November 14, 2020

You are given a string s consisting only of characters 'a' and 'b'.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Constraints:

1 <= s.length <= 10⁵
s[i] is 'a' or 'b'.

Solution: DP

dp[i][0] := min # of dels to make s[0:i] all ‘a’s;
dp[i][1] := min # of dels to make s[0:i] ends with 0 or mode ‘b’s

if s[i-1] == ‘a’:
dp[i + 1][0] = dp[i][0], dp[i + 1][1] = min(dp[i + 1][0], dp[i][1] + 1)
else:
dp[i + 1][0] = dp[i][0] + 1, dp[i + 1][1] = dp[i][1]

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

C++

// Author: Huahua

class Solution {

public:

int minimumDeletions(string s) {

// const int n = s.length();

// dp[i][0] := min # of dels to make s[0:i] all 'a's;

// dp[i][1] := min # of dels to make s[0:i] ends with 0+ 'b's

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

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

// if (s[i] == 'a') {

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

// dp[i + 1][1] = min(dp[i + 1][0], dp[i][1] + 1);

// } else {

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

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

// }

// return min(dp[n][0], dp[n][1]);

int a = 0, b = 0;

for (char c : s) {

if (c == 'a') b = min(a, b + 1);

else ++a;

}

return min(a, b);

}

};

花花酱 LeetCode 1641. Count Sorted Vowel Strings

By zxi on November 1, 2020

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

Solution: DP

dp[i][j] := # of strings of length i ends with j.

dp[i][j] = sum(dp[i – 1][[k]) 0 <= k <= j

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

C++/O(n) Space

class Solution {

public:

int countVowelStrings(int n) {

// dp[i][j] = # of strings of length i ends with j

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

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

int s = 0;

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

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

dp[i][j] = s;

}

return accumulate(begin(dp[n]), end(dp[n]), 0);

}

};

C++/O(1) Space

class Solution {

public:

int countVowelStrings(int n) {

// dp([i])[j] = # of strings of length i ends with j

vector<int> dp(5, 1);

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

for (int j = 4; j >= 0; --j)

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

dp[j] += dp[k];

return accumulate(begin(dp), end(dp), 0);

}

};