Posts tagged as “dp”

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

花花酱 LeetCode 375. Guess Number Higher or Lower II

By zxi on March 13, 2020

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution: DP

Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.

dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.

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

C++

// Author: Huahua

class Solution {

public:

int getMoneyAmount(int n) {

constexpr int kInf = 1e9;

vector<vector<int>> cache(n + 2, vector<int>(n + 2, kInf));

function<int(int, int)> dp = [&](int l, int r) {

int& ans = cache[l][r];

if (l >= r) return 0;

if (ans != kInf) return ans;

for (int x = l; x <= r; ++x)

ans = min(ans, x + max(dp(l, x - 1), dp(x + 1, r)));

return ans;

};

return dp(1, n);

}

};

Python3

# Author: Huahua

class Solution:

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

@lru_cache(maxsize=None)

def dp(l, r):

return min([k + max(dp(l, k - 1), dp(k + 1, r))

for k in range(l, r + 1)]) if l < r else 0

return dp(1, n)

花花酱 LeetCode 1359. Count All Valid Pickup and Delivery Options

By zxi on February 23, 2020

Given n orders, each order consist in pickup and delivery services.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

1 <= n <= 500

Solution: Combination

Let dp[i] denote the number of valid sequence of i nodes.

For i-1 nodes, the sequence length is 2(i-1).
For the i-th nodes,
If we put Pi at index = 0, then we can put Di at 1, 2, …, 2i – 2 => 2i-1 options.
If we put Pi at index = 1, then we can put Di at 2,3,…, 2i – 2 => 2i – 2 options.
…
If we put Pi at index = 2i-1, then we can put Di at 2i – 1=> 1 option.
There are total (2i – 1 + 1) / 2 * (2i – 1) = i * (2*i – 1) options

dp[i] = dp[i – 1] * i * (2*i – 1)

dp[i] = 2n! / 2^n

C++

// Author: Huahua

class Solution {

public:

int countOrders(int n) {

constexpr int kMod = 1e9 + 7;

long ans = 1;

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

ans = ans * i * (2 * i - 1) % kMod;

return ans;

}

};

花花酱 LeetCode 1349. Maximum Students Taking Exam

By zxi on February 9, 2020

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..

Students must be placed in seats in good condition.

Example 1:

Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

seats contains only characters '.' and'#'.
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8

Solution 1: DFS (TLE)

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

Solution 2: DP

Since how to fill row[i+1] only depends on row[i]’s state, we can define

dp[i][s] as the max # of students after filling i rows and s (as a binary string) is the states i-th row.

dp[i+1][t] = max{dp[i][s] + bits(t)} if row[i] = s && row[i +1] = t is a valid state.

Time complexity: O(m*2^(n+n)*n) = O(2^22)
Space complexity: O(m*2^n) = O(2^11) -> O(2^n)

C++

// Author: Huahua

class Solution {

public:

int maxStudents(vector<vector<char>>& seats) {

int m = seats.size();

int n = seats[0].size();

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

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

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

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

bool flag = true;

for (int j = 0; j < n && flag; ++j) {

if (!(c & (1 << j))) continue;

if (seats[i][j] == '#') flag = false;

bool l = j == 0 ? false : (c & (1 << (j - 1)));

bool r = j == n - 1 ? false : (c & (1 << (j + 1)));

bool ul = (j == 0 || i == 0) ? false : (l & (1 << (j - 1)));

bool ur = (j == n - 1 || i == 0) ? false : (l & (1 << (j + 1)));

if (l || r || ul || ur) flag = false;

}

if (flag)

dp[i + 1][c] = max(dp[i + 1][c], dp[i][l] + __builtin_popcount(c));

}

return *max_element(begin(dp[m]), end(dp[m]));

}

};

C++

// Author: Huahua

class Solution {

public:

int maxStudents(vector<vector<char>>& seats) {

const int m = seats.size();

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

vector<int> s(m + 1);

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

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

s[i] |= (seats[i - 1][j] == '.') << j;

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

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

for (int c = s[i];;c = (c - 1) & s[i]) {

if (c & (c >> 1)) continue;

for (int l = s[i - 1];;l = (l - 1) & s[i - 1]) {

if (!(l & (c >> 1)) && !((l >> 1) & c))

dp[i][c] = max(dp[i][c], dp[i - 1][l] + __builtin_popcount(c));

if (l == 0) break;

}

if (c == 0) break;

}

return *max_element(begin(dp[m]), end(dp[m]));

}

};

花花酱 LeetCode 1344. Jump Game V

By zxi on February 1, 2020

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Example 4:

Input: arr = [7,1,7,1,7,1], d = 2
Output: 2

Example 5:

Input: arr = [66], d = 1
Output: 1

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

Solution: Recursion w/ Memoization

dp(i) = max{1, max{dp(j) + 1}}, if i can jump to j.
ans = max(dp(i))

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

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

int n = a.size();

vector<int> m(n);

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

if (m[i]) return m[i];

int ans = 1;

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

ans = max(ans, dp(j) + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

ans = max(ans, dp(j) + 1);

return m[i] = ans;

};

int ans = 0;

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

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

return ans;

}

};

Solution 2: DP

Time complexity: O(nlogn + n*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

const int n = a.size();

vector<pair<int, int>> m(n); // <height, index>

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

m[i] = {a[i], i};

// Solve from the lowest bar.

sort(begin(m), end(m));

vector<int> dp(n, 1);

for (auto [v, i] : m) {

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

dp[i] = max(dp[i], dp[j] + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

dp[i] = max(dp[i], dp[j] + 1);

}

return *max_element(begin(dp), end(dp));

}

};