Dynamic Programming
10. Regular Expression Matching
Implement regular expression matching with support for '.' and ''. '.' Matches any single character. '' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<bool>> dp(m+1, vector<bool>(n+1));
dp[0][0] = true;
for (size_t i = 1; i < n; ++i) {
dp[0][i+1] = p[i] == '*' && dp[0][i-1];
}
for (size_t i = 1; i <= m; ++i) {
for (size_t j= 1; j <= n; ++j) {
if (p[j-1] != '*')
dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
else {
dp[i][j] = (dp[i][j - 2] || dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'));
}
}
}
return dp[m][n];
// int i = 0, j = 0;
// if (n == 0) return m == 0;
// if (n == 1) return m == 1 && (s[0] == p[0] || p[0] == '.');
// if (p[1] != '*') {
// return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), t.substr(1));
// }
}
};
44. Wildcard Matching
Implement wildcard pattern matching with support for '?' and ''. '?' Matches any single character. '' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;
for (int j = 1; j <=n; ++j) {
dp[0][j] = p[j-1] == '*' && dp[0][j-1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] != '*') {
dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
} else {
dp[i][j] = dp[i][j-1] || dp[i-1][j];
}
}
}
return dp[m][n];
}
};
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
class Solution {
public:
int numDecodings(string s) {
int len = s.size();
if (!len) return 0;
vector<int> ways(len + 1, 1);
if (s[0] == '0') return 0;
for (int i = 1; i < len; ++i) {
if (s[i] == '0'){
if (s[i - 1] == '0' || stoi(s.substr(i-1, 2)) > 26) return 0;
ways[i + 1] = ways[i - 1];
}
else if (s[i-1] != '0' && stoi(s.substr(i-1, 2)) <= 26) ways[i+1] = ways[i] + ways[i-1];
else {
ways[i + 1] = ways[i];
}
}
return ways[len];
}
};
96. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
class Solution {
public:
int numTrees(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
dp[i] += dp[j]*dp[i-j-1];
}
}
return dp[n];
}
};
95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example, Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n <= 0) return {};
return generateTrees(1, n);
}
vector<TreeNode*> generateTrees(int start, int end) {
vector<TreeNode*> res;
if (start > end) return {nullptr};
for (int i = start; i <= end; ++i) {
auto left = generateTrees(start, i - 1);
auto right = generateTrees(i+1, end);
for (auto l : left){
for (auto r : right) {
TreeNode* root = new TreeNode(i);
root->left = l;
root->right = r;
res.push_back(root);
}
}
}
return res;
}
};
97. Interleaving String
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.
BFS 和 DFS 的解法都是4ms, DP的解法是12ms
class Solution { // DP
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3) return false;
vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));
for (size_t i = 0; i <= len1; ++i) {
for (size_t j = 0; j <= len2; ++j) {
if (i == 0 && j == 0) dp[i][j] = true;
else if (i == 0) {
dp[i][j] = dp[i][j-1] && (s3[i+j-1] == s2[j-1]);
} else if (j == 0) {
dp[i][j] = dp[i-1][j] && (s3[i+j-1] == s1[i-1]);
} else {
dp[i][j] = (dp[i][j-1] && (s3[i+j-1] == s2[j-1])) || (dp[i-1][j] && (s3[i+j-1] == s1[i-1])) ;
}
}
}
return dp[len1][len2];
}
};
class Solution { // dfs
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3) return false;
vector<vector<bool>> isInvalid(len1 + 1, vector<bool>(len2 + 1, false));
return dfs(s1, s2, s3, 0, 0, 0, isInvalid);
}
bool dfs(const string& s1, const string& s2, const string& s3, int i, int j, int k, vector<vector<bool>>& isInvalid) {
if (isInvalid[i][j]) return false;
if (k == s3.size()) return true;
bool valid = (i < s1.size() && s1[i] == s3[k] && dfs(s1, s2, s3, i+1, j, k+1, isInvalid)) ||
(j < s2.size() && s2[j] == s3[k] && dfs(s1, s2, s3, i, j+1, k+1, isInvalid));
isInvalid[i][j] = !valid;
return valid;
}
};
class Solution { // bfs
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3) return false;
// unordered_set<int> visited;
vector<vector<bool>> visited(len1 + 1, vector<bool>(len2 + 1, false));
queue<pair<int, int>> q;
q.push({-1, -1});
while (!q.empty()) {
auto cur = q.front(); q.pop();
int i = cur.first + 1;
int j = cur.second + 1;
if (i == len1 && j == len2) return true;
if (i + j < len3) {
char next = s3[i+j];
if (i < len1 && s1[i] == next) {
if (!visited[i+1][j]) {
q.push({i, j-1});
visited[i+1][j] = true;
}
}
if (j < len2 && s2[j] == next) {
if (!visited[i][j+1]) {
q.push({i-1, j});
visited[i][j+1] = true;
}
}
}
}
return false;
}
};
115. Distinct Subsequences
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.
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size();
int n = t.size();
if (m == 0) return n == 0;
if (n == 0) return 1;
vector<vector<int>> dp(m+1, vector<int>(n+1));
for (int i = 0; i < m; ++i) dp[i][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i] == t[j]) {
dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
} else {
dp[i+1][j+1] = dp[i][j+1];
}
}
}
return dp[m][n];
}
};
132. Palindrome Partitioning II
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.
class Solution {
public:
int minCut(string s) {
size_t len = s.size();
vector<int> dp(len+1);
for (size_t i = 0; i < len + 1; ++i) dp[i] = i - 1;
for (int i = 0; i < len; ++i) {
for (int j = 0; j <= i && i + j < len && s[i-j] == s[i+j]; ++j)
dp[i+j+1] = min(dp[i+j+1], 1 + dp[i-j]);
for (int j = 1; i -j + 1 >= 0 && j + i < len && s[i-j+1] == s[i+j]; ++j)
dp[i+j+1] = min(dp[i+j+1], 1 + dp[i-j+1]);
}
return dp[len];
}
};
139. Word Break
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".
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
size_t n = s.size();
if (wordDict.find(s) != wordDict.end()) return true;
vector<bool> dp(n+1);
dp[0] = true;
for (size_t i = 1; i <= n; ++i) {
for (int j = i - 1; j >=0; --j) {
if (dp[j]) {
string word = s.substr(j, i - j);
if (wordDict.find(word) != wordDict.end()) {
dp[i] = true;
break;
}
}
}
}
return dp[n];
}
};
188. Best Time to Buy and Sell Stock IV
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).
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
size_t len = prices.size();
if (len < 2 || k <= 0) return 0;
int res = 0;
if (2*k >= len) {
for (size_t i = 1; i < len; ++i) {
if (prices[i] > prices[i-1]) res += prices[i] - prices[i-1];
}
return res;
}
/**
* dp[i, j] represents the max profit up until prices[j] using at most i transactions.
* dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] }
* = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
* dp[0, j] = 0; 0 transactions makes 0 profit
* dp[i, 0] = 0; if there is only one price data point you can't make any transaction.
*/
vector<vector<int>> dp(k+1, vector<int>(len));
for (int i = 1; i <= k; ++i) {
int local_max = dp[i-1][0] - prices[0];
for (int j = 1; j < len; ++j) {
dp[i][j] = max(dp[i][j-1], prices[j] + local_max);
local_max = max(local_max, dp[i-1][j] - prices[j]);
}
}
return dp[k][len-1];
}
};
221. Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0Return 4.
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (!matrix.size() || !matrix[0].size()) return 0;
size_t m = matrix.size();
size_t n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n));
int max_size = 0;
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (i == 0 || j == 0) dp[i][j] = matrix[i][j] - '0';
else if (matrix[i][j] == '1') {
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
max_size = max(max_size, dp[i][j]);
}
}
return max_size * max_size;
}
};
276 Paint Fence
There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.
Note: n and k are non-negative integers.
class Solution {
public:
int numWays(int n, int k) {
if (n <= 0 || k <= 0) return 0;
if (n == 1) return k;
if (k == 1) return n <= 2;
int same = k;
int diff = k*(k-1);
for (int i = 2; i < n; ++i) {
int pre = diff;
diff = (same + diff) * (k - 1);
same = pre;
}
return same + diff;
}
};
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
class Solution_v2 {
public:
int numSquares(int n) {
if (n <= 0) return 0;
vector<int> res(n + 1, INT_MAX);
res[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j*j <= i; j++) {
if (j*j == i) {
res[i] = 1;
} else {
res[i] = min(res[i], res[i - j*j] + 1);
}
}
}
return res[n];
}
};
309. Best Time to Buy and Sell Stock with Cooldown
class Solution {
public:
int maxProfit(vector<int>& prices) {
size_t len = prices.size();
if (len < 2) return 0;
vector<int> buy(len);
vector<int> sell(len);
vector<int> cool(len);
buy[0] = -prices[0];
for (int i = 1; i < len; ++i) {
cool[i] = sell[i-1];
buy[i] = max(cool[i-1] - prices[i], buy[i-1]);
sell[i] = max(buy[i-1] + prices[i], sell[i-1]);
}
return max(sell[len-1], cool[len-1]);
}
};
312 Burst Balloons
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
class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> n(nums);
size_t N = nums.size();
n.emplace(n.begin(), 1);
n.push_back(1);
vector<vector<int>> dp(n.size(), vector<int>(n.size()));
for (size_t len = 1; len <= N; ++len) {
for (size_t start = 1; start <= N - len + 1; ++start) {
size_t end = start + len - 1;
int largest = 0;
for (size_t final = start; final <= end; ++final) {
int coins = dp[start][final-1] + dp[final+1][end];
coins += n[start-1] * n[final] * n[end+1];
largest = max(largest, coins);
}
dp[start][end] = largest;
}
}
return dp[1][N];
}
};
class Solution {
public:
int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
int len = nums.size();
vector<vector<int>> dp(len, vector<int>(len));
return burst(dp, nums, 0, len-1);
}
int burst(vector<vector<int>>& memo, vector<int>& nums, int left, int right) {
if (left + 1 == right) return 0;
if (memo[left][right]) return memo[left][right];
int res = 0;
for (int i = left + 1; i < right; ++i) {
res = max(res, nums[left] * nums[i] * nums[right] + burst(memo, nums, left, i) + burst(memo, nums, i, right));
}
memo[left][right] = res;
return res;
}
};
322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)
Example 2: coins = [2], amount = 3 return -1.
Note: You may assume that you have an infinite number of each kind of coin.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount <= 0 || coins.size() == 0) return 0;
vector<int> dp(amount + 1, INT_MAX);
// sort(coins.begin(), coins.end());
// int min_val = coins[0];
// for (auto coin : coins) if (coin <= amount) dp[coin] = 1;
for (int i = 1; i <= amount; ++i) {
for (auto coin : coins) {
if (coin == i) {
dp[i] = 1;
break;
}
if (coin < i) {
if (dp[i-coin] != INT_MAX)
dp[i] = min(dp[i-coin] + 1, dp[i]);
}
}
}
if (dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};
Egg drop problem
given a maximum number of drops d, and a supply of b light bulbs, what is the tallest building that we can handle?
Consider the first drop from the as-yet-unknown optimal floor k. If the bulb breaks, then by Property 1 (and 3) above, there must be at most f(d-1,b-1) floors below floor k. If the bulb does not break, then by Property 2 (and 3), there must be at most f(d-1,b) floors above floor k. Thus, f(d,b) satisfies the following recurrence relation:
f(d,b) = f(d-1,b-1) + 1 + f(d-1,b)
f(d,0) = f(0,b) = 0
More explanation from this link
You’re right, either the bulb will break or it won’t. We aren’t saying that the bulb breaks and does not break. It’s either-or… but we need to be able to successfully find the “critical floor” in either case. Recall what the function f(d,b) computes: the maximum number of contiguous floors among which we can distinguish the critical floor in d drops using b bulbs. Then think of the two f() expressions on the right-hand side as breaking down the original problem into the two possible subproblems, depending on the outcome of the first (optimally-placed) drop.
It might help to consider an explicit example. Consider a building with 105 floors, and assume that we have two light bulbs, and that we get at most 14 drops. (Note that f(14,2)=105.) We should drop the first bulb from the 14th floor. If it breaks, then you can think of us being left with a “shorter building” consisting of the lower 13 floors, one remaining bulb, and 13 more drops (i.e., f(13,1)=13). If it does not break, then our “shorter building” consists of the 91 floors above us, also with 13 more drops, but still with 2 bulbs left (i.e., f(13,2)=91).
int GetHeight(int cases, int drops) {
vector<vector<int>> F(cases + 1, vector<int>(drops + 1, -1));
return GetHeightHelper(cases, drops, &F);
}
int GetHeightHelper(int cases, int drops, vector<vector<int>>* F) {
if (cases == 0 || drops == 0) {
return 0;
} else if (cases == 1) {
return drops;
} else {
if ((*F)[cases][drops] == -1) {
(*F)[cases][drops] = GetHeightHelper(cases, drops - 1, F) +
GetHeightHelper(cases - 1, drops - 1, F) + 1;
}
return (*F)[cases][drops];
}
}
Minimum Adjustment Cost
Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.
If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
Notice
You can assume each number in the array is a positive integer and not greater than 100.
Example
Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal.Return 2.
int MinAdjustmentCost(vector<int> A, int target) {
// write your code here
size_t n = A.size();
vector<vector<int>> f(n+1, vector<int>(101, INT_MAX));
for (int i = 0; i <=100; ++i) f[0][i] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= 100; ++j) {
if (f[i-1][j] != INT_MAX) {
for (int k = 0; k <= 100; ++k) {
if (abs(j - k) <= target) {
f[i][k] = min(f[i][k], f[i-1][j] + abs(A[i-1] - k));
}
}
}
}
}
int res = INT_MAX;
for (int i = 0; i <= 100; ++i) {
res = min(res, f[n][i]);
}
return res;
}