Posts tagged as “dp”

花花酱 LeetCode 1425. Constrained Subset Sum

By zxi on April 26, 2020

Given an integer array nums and an integer k, return the maximum sum of a non-empty subset of that array such that for every two consecutive integers in the subset, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subset of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subset is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution: DP / Sliding window / monotonic queue

dp[i] := max sum of a subset that include nums[i]
dp[i] := max(dp[i-1], dp[i-2], …, dp[i-k-1], 0) + nums[i]

C++

// Author: Huahua

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

multiset<int> s{INT_MIN};

int ans = INT_MIN;

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

if (i > k) s.erase(s.equal_range(dp[i - k - 1]).first);

dp[i] = max(*rbegin(s), 0) + nums[i];

s.insert(dp[i]);

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

}

return ans;

}

};

Use a monotonic queue to track the maximum of a sliding window dp[i-k-1] ~ dp[i-1].

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

C++

// Author: Huahua 184 ms

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

deque<int> q;

int ans = INT_MIN;

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

if (i > k && q.front() == i - k - 1)

q.pop_front();

dp[i] = (q.empty() ? 0 : max(dp[q.front()], 0))

+ nums[i];

while (!q.empty() && dp[i] >= dp[q.back()])

q.pop_back();

q.push_back(i);

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

}

return ans;

}

};

花花酱 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

By zxi on April 20, 2020

Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

arr has exactly n integers.
1 <= arr[i] <= m where (0 <= i < n).
After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Example 4:

Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

Input: n = 37, m = 17, k = 7
Output: 418930126

Constraints:

1 <= n <= 50
1 <= m <= 100
0 <= k <= n

Solution: DP

dp[n][m][k] := ways to build given n,m,k.

dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
dp[1][m][1] = m
dp[n][m][k] = 0 if k < 1 or k > m or k > n

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

C++

// Author: Huahua

int mem[51][101][51] = {0};

class Solution {

public:

int numOfArrays(int n, int m, int k) {

const int kMod = 1e9 + 7;

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

if (k < 1 || k > m || k > n) return 0;

if (n == 1 && k == 1) return m;

if (mem[n][m][k]) return mem[n][m][k];

long ans = 0;

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

ans += dp(n - 1, m, k);

ans += dp(n - 1, i - 1, k - 1);

ans -= dp(n - 1, i - 1, k);

ans = (ans + kMod) % kMod;

}

return mem[n][m][k] = ans;

};

return dp(n, m, k);

}

};

花花酱 LeetCode 1416. Restore The Array

By zxi on April 18, 2020

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k. There can be multiple ways to restore the array.

Return the number of possible array that can be printed as a string s using the mentioned program.

The number of ways could be very large so return it modulo 10^9 + 7

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

Example 4:

Input: s = "2020", k = 30
Output: 1
Explanation: The only possible array is [20,20]. [2020] is invalid because 2020 > 30. [2,020] is ivalid because 020 contains leading zeros.

Example 5:

Input: s = "1234567890", k = 90
Output: 34

Constraints:

1 <= s.length <= 10^5.
s consists of only digits and doesn’t contain leading zeros.
1 <= k <= 10^9.

Solution: DP

dp[i] := # of ways to restore the array for s[i:n].

dp[i] = sum(dp[j]), where 0 < j < n, int(s[i:j]) <= k, s[i] != 0

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

Top-down

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(string s, int k) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

vector<int> mem(n, -1);

// dp(i) returns # of ways for s[i:n]

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

if (i == n) return 1;

if (s[i] == '0') return 0;

if (mem[i] >= 0) return mem[i];

long num = 0;

int ans = 0;

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

num = num * 10 + (s[j - 1] - '0');

if (num > k) break;

ans = (ans + dp(j)) % kMod;

}

return mem[i] = ans;

};

return dp(0);

}

};

bottom-up

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(string s, int k) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

vector<int> dp(n + 1); // # of ways for s[i:n]

dp.back() = 1;

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

if (s[i] == '0') continue;

long num = 0;

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

num = num * 10 + (s[j - 1] - '0');

if (num > k) break;

dp[i] = (dp[i] + dp[j]) % kMod;

}

return dp[0];

}

};

花花酱 LeetCode 1411. Number of Ways to Paint N × 3 Grid

By zxi on April 12, 2020

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:

Example 2:

Input: n = 2
Output: 54

Example 3:

Input: n = 3
Output: 246

Example 4:

Input: n = 7
Output: 106494

Example 5:

Input: n = 5000
Output: 30228214

Constraints:

n == grid.length
grid[i].length == 3
1 <= n <= 5000

Solution: DP

dp[i][0] := # of ways to paint i rows with 2 different colors at the i-th row
dp[i][1] := # of ways to paint i rows with 3 different colors at the i-th row
dp[1][0] = dp[1][1] = 6
dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 2
dp[i][1] = dp[i-1][0] * 2 + dp[i-1][1] * 2

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

C++

// Author: Huahua

class Solution {

public:

int numOfWays(int n) {

constexpr int kMod = 1e9 + 7;

// dp[i][0] = # of ways to paint i rows with i-th row has 2 colors (e.g. 121)

// dp[i][1] = # of ways to paint i rows with i-th row has 3 colors (e.g. 123)

// dp[1][0] = dp[1][1] = 6.

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

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

// 121 => 2 colors x 3 {212, 232, 313}, 3 colors x 2 {213, 312}

// 123 => 2 colors x 2 {212, 232}, 3 colors x 2 {231, 312}

dp[i][0] = (dp[i - 1][0] * 3 + dp[i - 1][1] * 2) % kMod;

dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1] * 2) % kMod;

}

return (dp[n][0] + dp[n][1]) % kMod;

}

};

Python3

# Author: Huahua

class Solution:

def numOfWays(self, n: int) -> int:

kMod = 10**9 + 7

dp2, dp3 = 6, 6

for i in range(1, n):

t2, t3 = dp2 * 3 + dp3 * 2, dp2 * 2 + dp3 * 2

dp2, dp3 = t2 % kMod, t3 % kMod

return (dp2 + dp3) % kMod

Solution 2: DP w/ Matrix Chain Multiplication

ans = {6, 6} * {{3, 2}, {2,2}} ^ (n-1)

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

C++

// Author: Huahua

class Solution {

public:

int numOfWays(int n) {

constexpr long kMod = 1e9 + 7;

vector<vector<long>> ans{{6, 6}}; // 1x2

vector<vector<long>> M{{3, 2},{2,2}}; // 2x2

auto mul = [kMod](const vector<vector<long>>& A,

const vector<vector<long>>& B) {

const int m = A.size(); // m * n

const int n = B.size(); // n * p

const int p = B[0].size();

vector<vector<long>> C(m, vector<long>(p));

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

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

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

C[i][j] += (A[i][k] * B[k][j]) % kMod;

return C;

};

--n;

while (n) {

if (n & 1) ans = mul(ans, M); // ans = ans * M;

M = mul(M, M); // M = M^2

n >>= 1;

}

// ans = ans0 * M^(n-1)

return (ans[0][0] + ans[0][1]) % kMod;

}

};

花花酱 LeetCode 87. Scramble String

By zxi on March 14, 2020

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Solution: Recursion

isScramble(s1, s2)
if s1 == s2: return true
if sorted(s1) != sroted(s2): return false
We try all possible partitions:

s1[0:l] v.s s2[0:l] && s1[l:] vs s2[l:]
s1[0:l] vs s2[L-l:l] && s1[l:] vs s2[0:L-l]

Time complexity: O(n^5)
Space complexity: O(n^4)

C++

class Solution {

public:

bool isScramble(string_view s1, string_view s2) {

const int l = s1.length();

if (s1 == s2) return true;

if (freq(s1) != freq(s2)) return false;

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

if (isScramble(s1.substr(0, i), s2.substr(0, i))

&& isScramble(s1.substr(i), s2.substr(i))

|| isScramble(s1.substr(0, i), s2.substr(l - i, i))

&& isScramble(s1.substr(i), s2.substr(0, l - i)))

return true;

return false;

}

private:

vector<int> freq(string_view s) {

vector<int> f(26);

for (char c : s) ++f[c - 'a'];

return f;

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None) # optional

def isScramble(self, s1: str, s2: str) -> bool:

if s1 == s2: return True

# important, TLE if commneted out

if Counter(s1) != Counter(s2): return False

L = len(s1)

for l in range(1, L):

if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]):

return True

if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]):

return True

return False