Posts published in “Dynamic Programming”

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

}

};