Posts tagged as “dp”

花花酱 LeetCode 1235. Maximum Profit in Job Scheduling

By zxi on October 24, 2019

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:


Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solution: DP + binary search

Sort jobs by ending time.
dp[t] := max profit by end time t.

for a job = (s, e, p)
dp[e] = dp[u] + p, u <= s, and if dp[u] + p > last_element in dp.

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

C++

// Author: Huahua

class Solution {

public:

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {

const int n = startTime.size();

vector<vector<int>> jobs(n);

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

jobs[i] = {endTime[i], startTime[i], profit[i]};

sort(begin(jobs), end(jobs));

int ans = 0;

map<int, int> m{{0, 0}}; // {end_time -> max_profit}

for (const auto& job : jobs) {

int p = prev(m.upper_bound(job[1]))->second + job[2];

if (p > rbegin(m)->second) {

m[job[0]] = p;

}

return rbegin(m)->second;

}

};

花花酱 LeetCode 1230. Toss Strange Coins

By zxi on October 19, 2019

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:

Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Solution: DP

dp[i][j] := prob of j coins face up after tossing first i coins.
dp[i][j] = dp[i-1][j] * (1 – p[i]) + dp[i-1][j-1] * p[i]

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

C++

// Author: Huahua

class Solution {

public:

double probabilityOfHeads(vector<double>& prob, int target) {

const int n = prob.size();

vector<double> dp(target + 1);

dp[0] = 1.0;

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

for (int j = min(i + 1, target); j >= 0; --j)

dp[j] = dp[j] * (1 - prob[i]) + (j > 0 ? dp[j - 1] : 0) * prob[i];

return dp[target];

}

};

Solution 2: Recursion + Memorization

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

C++

// Author: Huahua

class Solution {

public:

double probabilityOfHeads(vector<double>& prob, int target) {

vector<vector<double>> mem(prob.size() + 1, vector<double>(target + 1, -1));

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

if (k > n || k < 0) return 0.0;

if (n == 0) return 1.0;

if (mem[n][k] >= 0) return mem[n][k];

const double p = prob[n - 1];

return mem[n][k] = p * dp(n - 1, k - 1) + (1 - p) * dp(n - 1, k);

};

return dp(prob.size(), target);

}

};

花花酱 LeetCode 1223. Dice Roll Simulation

By zxi on October 17, 2019

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.

Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls.

Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.

Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

Solutions: DP

Naive one:

def: dp[i][j][k] := # of sequences ends with k consecutive j after i rolls
Init: dp[1][*][1] = 1

transition:
dp[i][j][1] = sum(dp[i-1][p][*]), p != j
dp[i][j][k + 1] = dp[i-1][j]][k]

Time complexity: O(n*6*6*15)
Space complexity: O(n*6*15) -> O(6*15)

C++

// Author: Huahua

class Solution {

public:

int dieSimulator(int n, vector<int>& rollMax) {

constexpr int kMaxRolls = 15;

constexpr int kMod = 1e9 + 7;

// dp[i][j][k] := # of sequences ends with k consecutive j after i rolls

vector<vector<vector<int>>> dp(n + 1,

vector<vector<int>>(6, vector<int>(kMaxRolls + 1)));

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

dp[1][j][1] = 1; // 1 step, 1 dice, 1 way

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

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

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

for (int k = 1; k <= rollMax[p]; ++k)

if (p != j) // not the same dice

dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % kMod;

else if (k < rollMax[p]) // same dice, make sure k + 1 <= rollMax

dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k]) % kMod;

int ans = 0;

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

for (int k = 1; k <= rollMax[j]; ++k)

ans = (ans + dp[n][j][k]) % kMod;

return ans;

}

};

Solution 2: DP with compressed state

dp[i][j] := # of sequences of length i end with j
dp[i][j] := sum(dp[i-1]) – invalid

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

C++

// Author: Huahua

class Solution {

public:

int dieSimulator(int n, vector<int>& rollMax) {

constexpr int kMod = 1e9 + 7;

// dp[i][j] := # of sequences ends with j after i rolls

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

vector<int> sums(n + 1); // sums[i] := sum(dp[i])

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

sums[1] += dp[1][j] = 1; // 1 roll, 1 dice, 1 way

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

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

const int k = i - rollMax[j];

const int invalid = k <= 1 ? max(k, 0) : sums[k - 1] - dp[k - 1][j];

dp[i][j] = ((sums[i - 1] - invalid) % kMod + kMod) % kMod;

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

}

return sums[n];

}

};

花花酱 LeetCode 131. Palindrome Partitioning

By zxi on October 10, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution1: DP

dp[i] := ans of str[0:i]
dp[j] = { x + str[i:len] for x in dp[i] }, 0 <= i < len

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

C++

// Author: Huahua

bool isPalindrome(const string& s) {

const int n = s.length();

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

if (s[i] != s[n - 1 - i]) return false;

return true;

}

class Solution {

public:

vector<vector<string>> partition(string s) {

int n = s.length();

vector<vector<vector<string>>> dp(n + 1);

for (int len = 1; len <= n; ++len) {

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

string right = s.substr(i, len - i);

if (!isPalindrome(right)) continue;

if (i == 0) dp[len].push_back({right});

for (const auto& p : dp[i]) {

dp[len].push_back(p);

dp[len].back().push_back(right);

}

return dp[n];

}

};

Solution 2: DFS

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

C++

// Author: Huahua

bool isPalindrome(const string& s, int l, int r) {

while (l < r)

if (s[l++] != s[r--]) return false;

return true;

}

class Solution {

public:

vector<vector<string>> partition(string s) {

int n = s.length();

vector<vector<string>> ans;

vector<string> cur;

function<void(int)> dfs = [&](int start) {

if (start == n) {

ans.push_back(cur);

return;

}

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

if (!isPalindrome(s, start, i)) continue;

cur.push_back(s.substr(start, i - start + 1));

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 1220. Count Vowels Permutation

By zxi on October 5, 2019

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
Each vowel 'a' may only be followed by an 'e'.
Each vowel 'e' may only be followed by an 'a' or an 'i'.
Each vowel 'i' may not be followed by another 'i'.
Each vowel 'o' may only be followed by an 'i' or a 'u'.
Each vowel 'u' may only be followed by an 'a'.

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

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3:

Input: n = 5
Output: 68

Constraints:

1 <= n <= 2 * 10^4

Solution: DP

dp[i][c] := number of strings of length i ends with letter c
transition: follow the definition
ans = sum(dp[n])

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

C++

// Author: Huahua

class Solution {

public:

int countVowelPermutation(int n) {

constexpr int kMod = 1e9 + 7;

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

fill(begin(dp[1]), end(dp[1]), 1);

// 0: a, 1: e, 2: i, 3: o, 4: u

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

dp[i][1] += dp[i - 1][0]; // a -> e

dp[i][0] += dp[i - 1][1]; // e -> a

dp[i][2] += dp[i - 1][1]; // e -> i

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

if (j == 2) continue;

dp[i][j] += dp[i - 1][2]; // i -> *

}

dp[i][2] += dp[i - 1][3]; // o -> i

dp[i][4] += dp[i - 1][3]; // o -> u

dp[i][0] += dp[i - 1][4]; // u -> a

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

dp[i][j] %= kMod;

}

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

}

};

C++/O(1)

// Author: Huahua

class Solution {

public:

int countVowelPermutation(int n) {

constexpr int kMod = 1e9 + 7;

long a = 1, e = 1, i = 1, o = 1, u = 1;

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

long aa = (i + e + u) % kMod;

long ee = (i + a) % kMod;

long ii = (e + o) % kMod;

long oo = i % kMod;

long uu = (i + o) % kMod;

a = aa;

e = ee;

i = ii;

o = oo;

u = uu;

}

return (a + e + i + o + u) % kMod;

}

};

Solution 2: Matrix multiplication

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

C++

// Author: Huahua

constexpr int kMod = 1e9 + 7;

vector<vector<long>> operator*(const vector<vector<long>>& A, const vector<vector<long>>& B) {

int m = A.size();

int x = A[0].size();

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

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

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

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

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

C[i][j] += A[i][k] * B[k][j];

C[i][j] %= kMod;

}

return C;

}

class Solution {

public:

int countVowelPermutation(int n) {

vector<vector<long>> m{

{0, 1, 0, 0, 0}, // a

{1, 0, 1, 0, 0}, // e

{1, 1, 0, 1, 1}, // i

{0, 0, 1, 0, 1}, // o

{1, 0, 0, 0, 0} // u

};

vector<vector<long>> ans{{1}, {1}, {1}, {1}, {1}};

n -= 1;

while (n > 0) {

if (n % 2) ans = m * ans;

m = m * m;

n /= 2;

}

long sum = 0;

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

sum += ans[i][0];

return sum % kMod;

}

};