Posts published in “Dynamic Programming”

花花酱 LeetCode 1735. Count Ways to Make Array With Product

By zxi on January 23, 2021

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [n_i, k_i], find the number of different ways you can place positive integers into an array of size n_i such that the product of the integers is k_i. As the number of ways may be too large, the answer to the i^th query is the number of ways modulo 10⁹ + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the i^th query.

Example 1:

Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation: Each query is independent.
[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].
[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].
[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 10⁹ + 7 = 50734910.

Example 2:

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]

Constraints:

1 <= queries.length <= 10⁴
1 <= n_i, k_i <= 10⁴

Solution1: DP

let dp(n, k) be the ways to have product k of array size n.
dp(n, k) = sum(dp(n – 1, i)) where i is a factor of k and i != k.
base case:
dp(0, 1) = 1, dp(0, *) = 0
dp(i, 1) = C(n, i)
e.g.
dp(2, 6) = dp(1, 1) + dp(1, 2) + dp(1, 3)
= 2 + 1 + 1 = 4
dp(4, 4) = dp(3, 1) + dp(3, 2)
= dp(3, 1) + dp(2, 1)
= 4 + 6 = 10

Time complexity: O(sum(k_i))?
Space complexity: O(sum(k_i))?

C++

// Author: Huahua

class Solution {

public:

vector<int> waysToFillArray(vector<vector<int>>& queries) {

constexpr int kMod = 1e9 + 7;

int n = 0;

unordered_map<int, int> c, dp;

function<int(int, int)> cnk = [&](int n, int k) {

if (k > n) return 0;

if (k == 0 || k == n) return 1;

int& ans = c[(n << 16) | k];

if (!ans) ans = (cnk(n - 1, k - 1) + cnk(n - 1, k)) % kMod;

return ans;

};

function<int(int, int)> dfs = [&](int s, int k) -> int {

if (s == 0) return k == 1;

if (k == 1) return cnk(n, s);

int& ans = dp[(s << 16) | k];

if (ans) return ans;

for (int i = 1; i * i <= k; ++i) {

if (k % i) continue;

if (i != 1)

ans = (ans + dfs(s - 1, k / i)) % kMod;

if (i * i != k)

ans = (ans + dfs(s - 1, i)) % kMod;

}

return ans;

};

vector<int> ans;

for (const auto& q : queries) {

dp.clear();

n = q[0];

ans.push_back(dfs(n, q[1]));

}

return ans;

}

};

花花酱 LeetCode 1728. Cat and Mouse II

By zxi on January 17, 2021

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a grid of size rows x cols, where each element is a wall, floor, player (Cat, Mouse), or food.

Players are represented by the characters 'C'(Cat),'M'(Mouse).
Floors are represented by the character '.' and can be walked on.
Walls are represented by the character '#' and cannot be walked on.
Food is represented by the character 'F' and can be walked on.
There is only one of each character 'C', 'M', and 'F' in grid.

Mouse and Cat play according to the following rules:

Mouse moves first, then they take turns to move.
During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid.
catJump, mouseJump are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
Staying in the same position is allowed.
Mouse can jump over Cat.

The game can end in 4 ways:

If Cat occupies the same position as Mouse, Cat wins.
If Cat reaches the food first, Cat wins.
If Mouse reaches the food first, Mouse wins.
If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a rows x cols matrix grid and two integers catJump and mouseJump, return true if Mouse can win the game if both Cat and Mouse play optimally, otherwise return false.

Example 1:

Input: grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
Output: true
Explanation: Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

Example 2:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 4
Output: true

Example 3:

Input: grid = ["M.C...F"], catJump = 1, mouseJump = 3
Output: false

Example 4:

Input: grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
Output: false

Example 5:

Input: grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
Output: true

Constraints:

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] consist only of characters 'C', 'M', 'F', '.', and '#'.
There is only one of each character 'C', 'M', and 'F' in grid.
1 <= catJump, mouseJump <= 8

Solution: MinMax + Memoization

Time complexity: O(m^3 * n^3 * max(n, m))
Space complexity: O(m^3 * n^3)

state: [mouse_pos, cat_pos, turn]

C++

// Author: Huahua

class Solution {

public:

bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {

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

int mouse, cat, food;

for (int pos = 0; pos < m * n; ++pos)

switch (grid[pos / n][ pos % n]) {

case 'M': mouse = pos; break;

case 'C': cat = pos; break;

case 'F': food = pos; break;

default: break;

}

const vector<pair<int, int>> dirs{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

const int limit = m * n * 2;

vector<vector<vector<int>>> seen(m*n,

vector<vector<int>>(m*n, vector<int>(limit + 1, -1)));

function<bool(int, int, int)> dfs =

[&](int mouse, int cat, int d) -> bool {

const bool isCat = d & 1;

if (cat == food || cat == mouse || d >= limit) return isCat;

if (mouse == food) return !isCat;

int& ans = seen[mouse][cat][d];

if (ans != -1) return ans;

const int cur = isCat ? cat : mouse;

const int jumps = isCat ? catJump : mouseJump;

for (const auto& [dx, dy] : dirs)

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

const int x = (cur % n) + dx * j;

const int y = (cur / n) + dy * j;

const int pos = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == '#') break;

if (!dfs(isCat ? mouse : pos, isCat ? pos : cat, d + 1)) return ans = true;

}

return ans = false;

};

return dfs(mouse, cat, 0);

}

};

花花酱 LeetCode 1727. Largest Submatrix With Rearrangements

By zxi on January 17, 2021

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Example 4:

Input: matrix = [[0,0],[0,0]]
Output: 0
Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is 0 or 1.

Solution: DP + Sorting

Preprocess each column, for col j, matrix[i][j] := length consecutive ones of col j.

[0,0,1]    [0,0,1]
[1,1,1] => [1,1,2]
[1,0,1]    [2,0,3]

Then we enumerate ending row, for each ending row i, we sort row[i] in deceasing order

e.g. i = 2

[0,0,1]                  [-,-,-]
[1,1,2] sort by row 2 => [-,-,-]
[2,0,3]                  [3,2,0]

row[2][1] = 3, means there is a 3×1 all ones sub matrix, area = 3
row[2][2] = 2, means there is a 2×2 all ones sub matrix, area = 4.

Time complexity: O(m*n*log(n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int largestSubmatrix(vector<vector<int>>& matrix) {

const int m = matrix.size();

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

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

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

if (matrix[i][j]) matrix[i][j] += matrix[i - 1][j];

int ans = 0;

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

sort(rbegin(matrix[i]), rend(matrix[i]));

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

ans = max(ans, (j + 1) * matrix[i][j]);

}

return ans;

}

};

花花酱 LeetCode 1723. Find Minimum Time to Finish All Jobs

By zxi on January 10, 2021

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Solution 1: All subsets

dp[i][t] := min of max working time by assigning a subset of jobs s to the first i workers.

dp[i][t] = min{max(dp[i – 1][s], cost[s ^ t])} where s is a subset of t.

Time complexity: O(k*3^n)
Space complexity: O(k*2^n)

C++

// Author: Huahua

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

const int n = jobs.size();

int dp[13][4096];

memset(dp, 0x7f, sizeof(dp));

dp[0][0] = 0;

vector<int> cost(1 << n);

for (int t = 0; t < 1 << n; ++t) {

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

if (t >> j & 1) cost[t] += jobs[j];

dp[1][t] = cost[t]; // do jobs t by one worker

}

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

for (int t = 0; t < 1 << n; ++t)

for (int s = t; s; s = (s - 1) & t)

dp[i][t] = min(dp[i][t], max(dp[i - 1][s], cost[t ^ s]));

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

}

};

Solution 2: Search + Pruning

Time complexity: O(k^n)
Space complexity: O(k*n)

C++

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

vector<int> times(k);

int ans = INT_MAX;

function<void(int, int)> dfs = [&](int i, int cur) {

if (cur >= ans) return;

if (i == jobs.size()) {

ans = cur;

return;

}

unordered_set<int> seen;

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

if (!seen.insert(times[j]).second) continue;

times[j] += jobs[i];

dfs(i + 1, max(cur, times[j]));

times[j] -= jobs[i];

}

};

sort(rbegin(jobs), rend(jobs));

dfs(0, 0);

return ans;

}

};

花花酱 LeetCode 1713. Minimum Operations to Make a Subsequence

By zxi on January 3, 2021

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

Example 2:

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

Constraints:

1 <= target.length, arr.length <= 10⁵
1 <= target[i], arr[i] <= 10⁹
target contains no duplicates.

Solution: Reduce to LIS

The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.
Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problem to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.

e.g.
target: [6,4,8,1,3,2] => [0, 1, 2, 3, 4, 5]
array: [4,7,6,2,3,8,6,1] => [1,-1, 0, 5, 4, 2, 0, 3] => [1, 0, 5, 4, 2, 3]
and the LIS is [0, 2, 3] => [6, 8, 1], we need to insert the rest of the numbers.
Ans = len(target) – len(LIS)

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A, vector<int>& B) {

unordered_map<int, int> m;

for (int i = 0; i < A.size(); ++i)

m[A[i]] = i;

vector<int> dp;

for (int x : B) {

auto mit = m.find(x);

if (mit == end(m)) continue;

const int idx = mit->second;

if (dp.empty() || idx > dp.back())

dp.push_back(idx);

else

*lower_bound(begin(dp), end(dp), idx) = idx;

}

return A.size() - dp.size();

}

};

Python3

# Author: Huahua

class Solution:

def minOperations(self, A: List[int], B: List[int]) -> int:

m = {x: i for i, x in enumerate(A)}

dp = []

for x in B:

if x not in m: continue

if not dp or m[x] > dp[-1]: dp.append(m[x])

else: dp[bisect_left(dp, m[x])] = m[x]

return len(A) - len(dp)