# 188. Best Time to Buy and Sell Stock IV

Difficulty: Hard

Frequency: N/A

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k >= n / 2) return helper(prices);
vector<vector<int>> dp(k + 1, vector<int>(n, 0));
for (int i = 1; i <= k; i++) {
int tmpMax = -prices[0];
for (int j = 1; j < n; j++) {
dp[i][j] = max(dp[i][j - 1], tmpMax + prices[j]);
tmpMax = max(tmpMax, dp[i - 1][j - 1] - prices[j]);
}
}
return dp[k][n - 1];
}
int helper(vector<int>& prices) {
int n = prices.size(), result = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
result += prices[i] - prices[i - 1];
}
}
return result;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 139. Word Break

Difficulty: Medium

Frequency: N/A

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = `"leetcode"`,
dict = `["leet", "code"]`.

Return true because `"leetcode"` can be segmented as `"leet code"`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
if (wordDict.empty()) return false;
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (dp[j] == true) {
string word = s.substr(j, i - j);
if (wordDict.find(word) != wordDict.end()) {
dp[i] = true;
break;
}
}
}
}
return dp[n];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 312. Burst Balloons

Difficulty: Hard

Frequency: N/A

Given `n` balloons, indexed from `0` to `n-1`. Each balloon is painted with a number on it represented by array `nums`. You are asked to burst all the balloons. If the you burst balloon `i` you will get `nums[left] * nums[i] * nums[right]` coins. Here `left` and `right` are adjacent indices of `i`. After the burst, the `left` and `right` then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.
(2) 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100

Example:

Given `[3, 1, 5, 8]`

Return `167`

```    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167```

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> nums2(nums.size() + 2, 0);
int n = 1;
for (int num : nums) {
if (num > 0) nums2[n++] = num;
}
nums2[0] = nums2[n++] = 1;

vector<vector<int>> dp(n, vector<int>(n, 0));
for (int k = 2; k < n; k++) {
for (int left = 0; left < n - k; left++) {
int right = left + k;
for (int i = left + 1; i < right; i++) {
dp[left][right] = max(dp[left][right], nums2[left] * nums2[i] * nums2[right] + dp[left][i] + dp[i][right]);
}
}
}
return dp[0][n - 1];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 265. (Locked)Paint House II

Difficulty: Hard

Frequency: N/A

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs0 is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note: All costs are positive integers.

Follow up: Could you solve it in O(nk) runtime?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
int n = costs.size(), k = costs[0].size(), m1 = 0, m2 = 0;
vector<int> dp(k, 0);
for (int i = 0; i < n; i++) {
int t1 = m1, t2 = m2;
m1 = m2 = INT_MAX;
for (int j = 0; j < k; j++) {
dp[j] = (dp[j] != t1 ? t1 : t2) + costs[i][j];
if (m1 <= dp[j]) m2 = min(m2, dp[j]);
else {
m2 = m1;
m1 = dp[j];
}
}
}
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 174. Dungeon Game

Difficulty: Hard

Frequency: N/A

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path `RIGHT-> RIGHT -> DOWN -> DOWN`.

 -2 (K) -3 3 -5 -10 1 10 30 -5 (P)

Notes:

• The knight’s health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.empty()) return 0;
int m = dungeon.size(), n = dungeon[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[m][n - 1] = 1;
dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = need <= 0 ? 1 : need;
}
}
return dp[0][0];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 140. Word Break II

Difficulty: Hard

Frequency: N/A

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = `"catsanddog"`,
dict = `["cat", "cats", "and", "sand", "dog"]`.

A solution is `["cats and dog", "cat sand dog"]`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
private:
unordered_map<string, vector<string>> m;
vector<string> combine(string word, vector<string> prev) {
for (int i = 0; i < prev.size(); i++) prev[i] += " " + word;
return prev;
}
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
if (m.count(s)) return m[s];
vector<string> results;
if (wordDict.count(s)) results.push_back(s);
for (int i = 1; i < s.size(); i++) {
string word = s.substr(i);
if (wordDict.count(word)) {
string rem = s.substr(0, i);
vector<string> prev = combine(word, wordBreak(rem, wordDict));
results.insert(results.end(), prev.begin(), prev.end());
}
}
m[s] = results;
return results;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 132. Palindrome Partitioning II

Difficulty: Hard

Frequency: N/A

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

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = `"aab"`,
Return `1` since the palindrome partitioning `["aa","b"]` could be produced using 1 cut.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<int> cuts(n + 1, 0);
for (int i = 0; i <= n; i++) cuts[i] = i - 1;
for (int i = 0; i < n; i++) {
for (int j = 0; i - j >= 0 && i + j < n && s[i - j] == s[i + j]; j++) {
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1);
}
for (int j = 1; i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j]; j++) {
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j + 1] + 1);
}
}
return cuts[n];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 123. Best Time to Buy and Sell Stock III

Difficulty: Hard

Frequency: N/A

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (!n) return 0;
vector<int> leftProfit(n, 0);
int minPrice = prices[0], maxLeftProfit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxLeftProfit = max(maxLeftProfit, prices[i] - minPrice);
}
leftProfit[i] = maxLeftProfit;
}
int maxRightProfit = 0, maxProfit = leftProfit[n - 1], maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
if (prices[i] > maxPrice) {
maxPrice = prices[i];
} else {
maxRightProfit = max(maxRightProfit, maxPrice - prices[i]);
}
maxProfit = max(maxProfit, leftProfit[i] + maxRightProfit);
}
return maxProfit;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 115. Distinct Subsequences

Difficulty: Hard

Frequency: N/A

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

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).

Here is an example:
S = `"rabbbit"`, T = `"rabbit"`

Return `3`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
if (m < n) return 0;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int j = 0; j <= m; j++) dp[0][j] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i][j - 1] + (s[j - 1] == t[i - 1] ? dp[i - 1][j - 1] : 0);
}
}
return dp[n][m];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 097. Interleaving String

Difficulty: Hard

Frequency: N/A

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = `"aabcc"`,
s2 = `"dbbca"`,

When s3 = `"aadbbcbcac"`, return true.
When s3 = `"aadbbbaccc"`, return false.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (s3.size() != m + n) return false;
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i - 1];
} else {
dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1] ||
dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
}
}
}
return dp[m][n];
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn: