Posts published in “Dynamic Programming”

花花酱 LeetCode 879. Profitable Schemes

By zxi on July 28, 2018

Problem

There are G people in a gang, and a list of various crimes they could commit.

The i-th crime generates a profit[i] and requires group[i] gang members to participate.

If a gang member participates in one crime, that member can’t participate in another crime.

Let’s call a profitable scheme any subset of these crimes that generates at least P profit, and the total number of gang members participating in that subset of crimes is at most G.

How many schemes can be chosen? Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: 
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: 
To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

Note:

1 <= G <= 100
0 <= P <= 100
1 <= group[i] <= 100
0 <= profit[i] <= 100
1 <= group.length = profit.length <= 100

Solution: DP

Time complexity: O(KPG)

Space complexity: O(KPG)

C++

// Author: Huahua

// Running time: 64 ms

class Solution {

public:

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {

const int kMod = 1000000007;

const int K = group.size();

// dp[k][i][j]:= # of schemes of making profit i with j people by commiting first k crimes.

vector<vector<vector<int>>> dp(K + 1, vector<vector<int>>(P + 1, vector<int>(G + 1, 0)));

dp[0][0][0] = 1;

for (int k = 1; k <= K; ++k) {

const int p = profit[k - 1];

const int g = group[k - 1];

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

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

dp[k][i][j] = (dp[k - 1][i][j] + (j < g ? 0 : dp[k - 1][max(0, i - p)][j - g])) % kMod;

}

return accumulate(begin(dp[K][P]), end(dp[K][P]), 0LL) % kMod;

}

};

Space complexity: O(PG)

v1: Dimension reduction by copying.

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {

const int kMod = 1000000007;

const int K = group.size();

// dp[i][j]:= # of schemes of making profit i with j people.

vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));

dp[0][0] = 1;

for (int k = 1; k <= K; ++k) {

auto tmp = dp;

const int p = profit[k - 1];

const int g = group[k - 1];

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

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

tmp[i][j] = (tmp[i][j] + (j < g ? 0 : dp[max(0, i - p)][j - g])) % kMod;

dp.swap(tmp);

}

return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;

}

};

v2: Dimension reduction by using rolling array.

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {

const int kMod = 1000000007;

// dp[i][j]:= # of schemes of making profit i with j people.

vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));

dp[0][0] = 1;

const int K = group.size();

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

const int p = profit[k];

const int g = group[k];

for (int i = P; i >= 0; --i) {

const int ip = min(P, i + p);

for (int j = G - g; j >= 0; --j)

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

}

return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;

}

};

花花酱 LeetCode 877. Stone Game

By zxi on July 28, 2018

Problem

Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

Note:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.

Solution 1: min-max (TLE)

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: TLE 26/46 passed.

class Solution {

public:

bool stoneGame(vector<int>& piles) {

return score(piles, 0, piles.size() - 1) > 0;

}

private:

int score(const vector<int>& piles, int l, int r) {

if (l == r) return piles[l];

return max(piles[l] - score(piles, l + 1, r),

piles[r] - score(piles, l, r - 1));

}

};

Solution 2: min-max + memorization

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

m_ = vector<vector<int>>(n, vector<int>(n, INT_MIN));

return score(piles, 0, n - 1) > 0;

}

private:

vector<vector<int>> m_;

int score(const vector<int>& piles, int l, int r) {

if (l == r) return piles[l];

if (m_[l][r] == INT_MIN)

m_[l][r] = max(piles[l] - score(piles, l + 1, r),

piles[r] - score(piles, l, r - 1));

return m_[l][r];

}

};

Solution 3: min-max + DP

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

// dp[i][j] := max(your_stones - op_stones) for piles[i] ~ piles[j]

vector<vector<int>> dp(n, vector<int>(n, 0));

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

dp[i][i] = piles[i];

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

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

int j = i + l - 1;

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

}

return dp[0][n - 1] > 0;

}

};

O(n) Space

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

// dp[i] := max(your_stones - op_stones) for piles[i] to piles[i + l - 1]

vector<int> dp(piles);

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

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

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

return dp[0] > 0;

}

};

Problem

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:

Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Solution 1: DP

C++

// Author: Huahua

// Running time: 68 ms

// w/ Hashtable

// Time complexity: O(n^2)

// Space complexity: O(n^2)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_map<int, int> m;

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

m[A[i]] = i;

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break; // pruning 168 ms -> 68 ms

auto it = m.find(a_i);

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

int i = it->second;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 96 ms

// w / Binary Search

// Time complexity: O(n^2logn)

// Space complexity: O(n)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break;

auto it = lower_bound(begin(A), begin(A) + j, a_i);

int i = it - begin(A);

if (A[i] != a_i) continue;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n^3)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 172 ms

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_set<int> m(begin(A), end(A));

int ans = 0;

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

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

int a = A[i];

int b = A[j];

int c = a + b;

int l = 2;

while (m.count(c)) {

a = b;

b = c;

c = a + b;

ans = max(ans, ++l);

}

return ans;

}

};

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

By zxi on July 20, 2018

Problem

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.
All elements of each string will have an ASCII value in [97, 122].

Solution: DP

Time complexity: O(l1 * l2)

Space complexity: O(l1 * l2)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int minimumDeleteSum(string s1, string s2) {

const int l1 = s1.length();

const int l2 = s2.length();

// dp[i][j] := min delete sum of (s1.substr(0, i), s2.substr(0, j))

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

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

dp[i][0] = dp[i - 1][0] + s1[i - 1];

for (int j = 1; j <= l2; ++j)

dp[0][j] = dp[0][j - 1] + s2[j - 1];

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

for (int j = 1; j <= l2; ++j)

if (s1[i - 1] == s2[j - 1])

// keep s1[i - 1] and s2[j - 1]

dp[i][j] = dp[i - 1][j - 1];

else

dp[i][j] = min(dp[i - 1][j] + s1[i - 1], // delete s1[i - 1]

dp[i][j - 1] + s2[j - 1]); // delete s2[j - 1]

return dp[l1][l2];

}

};

Solution2: Recursion + Memorization

Time complexity: O(l1 * l2)

Space complexity: O(l1 * l2)

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int minimumDeleteSum(string s1, string s2) {

const int l1 = s1.length();

const int l2 = s2.length();

m_ = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, INT_MAX));

return dp(s1, l1, s2, l2);

}

private:

int dp(const string& s1, int i, const string& s2, int j) {

if (i == 0 && j == 0) return 0;

if (m_[i][j] != INT_MAX) return m_[i][j];

if (i == 0) // s1 is empty.

return m_[i][j] = dp(s1, i, s2, j - 1) + s2[j - 1];

if (j == 0) // s2 is empty

return m_[i][j] = dp(s1, i - 1, s2, j) + s1[i - 1];

if (s1[i - 1] == s2[j - 1]) // skip s1[i-1] / s2[j-1]

return m_[i][j] = dp(s1, i - 1, s2, j - 1);

return m_[i][j] = min(dp(s1, i - 1, s2, j) + s1[i - 1], // del s1[i-1]

dp(s1, i, s2, j - 1) + s2[j - 1]); // del s2[j-1]

}

vector<vector<int>> m_;

};

Problem

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:  As shown below, there are 3 ways you can generate "rabbit" from S. (The caret symbol ^ means the chosen letters) 
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:  As shown below, there are 5 ways you can generate "bag" from S. (The caret symbol ^ means the chosen letters)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^

Solution: DP

Time complexity: O(|s| * |t|)

Space complexity: O(|s| * |t|)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numDistinct(string s, string t) {

int ls = s.length();

int lt = t.length();

vector<vector<int>> dp(lt + 1, vector<int>(ls + 1));

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

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

for (int j = 1; j <= ls; ++j)

dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);

return dp[lt][ls];

}

};

Posts published in “Dynamic Programming”

花花酱 LeetCode 879. Profitable Schemes

Problem

Solution: DP

花花酱 LeetCode 877. Stone Game

Problem

Solution 1: min-max (TLE)

Solution 2: min-max + memorization

Solution 3: min-max + DP

Related Problems

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

Problem

Solution 1: DP

C++

C++ V2

Solution 2: HashTable

C++

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

Problem

Solution: DP

Solution2: Recursion + Memorization

Related Problems

花花酱 LeetCode 115. Distinct Subsequences

Problem

Solution: DP

Related Problems:

Posts published in “Dynamic Programming”

花花酱 LeetCode 879. Profitable Schemes

Problem

Solution: DP

花花酱 LeetCode 877. Stone Game

Problem

Solution 1: min-max (TLE)

Solution 2: min-max + memorization

Solution 3: min-max + DP

Related Problems

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

Problem

<img class="alignnone size-full wp-image-3274" src="http://zxi.mytechroad.com/blog/wp-content/uploads/2018/07/873-ep210.png" alt="" width="960" height="540"/>

Solution 1: DP

C++

C++ V2

Solution 2: HashTable

C++

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

Problem

Solution: DP

Solution2: Recursion + Memorization

Related Problems

花花酱 LeetCode 115. Distinct Subsequences

Problem

Solution: DP

Related Problems: