Dynamic Programming (Part 2)
| 877 |
You can first pick piles[i] or piles[j].
If you pick piles[i], your result will be piles[i] - dp[i + 1][j]
If you pick piles[j], your result will be piles[j] - dp[i][j - 1]
So we get:
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
We start from smaller subarray and then we use that to calculate bigger subarray.
309 Best Time to Buy and Sell Stock with Cooldown
int n = prices.size();
// sell[i] : maximum profit when the i-th day NOT hold the stock
vector<int> sell(n, 0);
// hold[i] : maximum profit when the i-th day hold the stock
vector<int> hold(n, 0);
Base Case:
sell[0] = 0;
hold[0] = -prices[0];
for (int i = 1; i < n; i++) {
// dp formula:
sell[i] = max(sell[i - 1], hold[i - 1] + prices[i]);
hold[i] = max(hold[i - 1], (i >= 2 ? sell[i - 2] : 0) - prices[i]);
}
return sell[n - 1];
712 Minimum ASCII Delete Sum for Two Strings
if (i == 0) // s1 is empty.
return memo[i][j] = dp(s1, i, s2, j - 1) + s2[j - 1];
if (j == 0) // s2 is empty
return memo[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 memo[i][j] = dp(s1, i - 1, s2, j - 1);
// else s1[i - 1] != s2[j - 1]
return memo[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]
392 Is Subsequence
dp[i][j] means whether s.substr(0, i) is the subsequence of t.substr(0, j)
Base Case:
vector<vector<int>> dp(m + 1, vector<int>(n + 1, false));
for (int j = 0; j < n; j++)
dp[0][j] = true; // empty string is subsequence of any string
dp formula:
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = dp[i][j - 1];
}
}
return dp[m][n];
714 Best Time to Buy and Sell Stock with Transaction Fee
On the ith day，If we sell the stock，then the profit we get is the profit from holding it in the (i -1)th day (otherwise we have nothing to sell), plus the current price and minus the fee. And compare it with sell it on the (i - 1) th day, choose the bigger one of the two ( if the sell it on the (i -1)th day makes a larger profix, we won't hold it until the ith day).
Let us look at the profit of not selling it on the ith day. Which is the profit from selling it yersterday and buy today (need to minus today's price), and hold it from the (i-1)th day to ith day. Choose the larger one of the two. If hold it yesterday makes a larger profit, we will hold it to today.
sold[0] = 0, hold[0] = -prices[0];
sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee);
hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]);
where i is from [1 to n -1]
| 646 |
(2) Define a dp array with all values initialized to 1.
(3) Base Case:
dp[0] = 1; // Optional
(4) DP formula:
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
}
}
(5) return dp[n - 1]
| 343 |
vector<int> dp(n + 1, 0);
dp[1] = 1, dp[2] = 1;
dp formula: for i in [ 3, n], for j in [1, i)
dp[i] = max(dp[i], max(j, dp[j]) * max((i - j), dp[i - j]));
638 Shopping Offers
DFS recursion.
650 2 Keys Keyboard
dp[i] means the minimum steps to generate i 'A'
vector<int> dp(n + 1, 0);Base Case: dp[1] = 0;
DP formula:
for (int i = 2; i <= n; i++) {
dp[i] = i; // worst case copy paste single char i times
for (int j = n - 1; j >= 2; j--) {
if (i % j != 0)
continue;
// min steps to generate [i/j] + generate j by pasting single char j times
dp[i] = min(dp[i], dp[i / j] + j);
}
}
| 494 |
dp[i][j] means the total number of ways that sum to 'j' using the first 'i' number vector<unordered_map<int, int> > dp(n + 1);
dp[0][0] = 1; // crucial for right answer
for (int i = 1; i <= n; i++) {
for (const auto& mp : dp[i - 1]) {
auto& sum = mp.first;
auto& count = mp.second;
dp[i][sum + nums[i - 1]] += count;
dp[i][sum - nums[i - 1]] += count;
}
}
return dp[n][S];
Note it is OK that sum - nums[i - 1] is negative, since the unordered_map key could be any value.
Game (min-max)
486 Predict the Winner
define dp[i][j] is the maximum score player 1 could win more than player 2.// Base Case: if only one element, player one can first choose it always.
for (int i = 0; i < n; i++)
dp[i][i] = nums[i];
// Build up from smaller interval range to large one, choose the one that makes
// a bigger delta between player 1 and 2.
// DP formula: dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
for (int diff = 1; diff < n; diff++) {
for (int i = 0; i < n - diff; i++) {
int j = i + diff;
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
813 Largest Sum of Averages
// dp[i][j]: Largest sum of averages for first j elements in A partitioned into i groups
vector<vector<double> > dp(K + 1, vector<double>(n + 1, 0.0));
vector<double> sums(n + 1, 0.0);
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + A[i - 1];
// Base Case
dp[1][i] = static_cast<double>(sums[i]) / i;
}
dp[k][i] = max(dp[k – 1][j] + sum(a[j] ~ a[i – 1]) / (i – j)) for j in k – 1,…,i-1.
that is find the best j such that maximize dp[k][i]
largest sum of partitioning first j elements (a[0] ~ a[j – 1]) into k – 1 groups (already computed)
+ average of a[j] ~ a[i – 1] (partition a[j] ~ a[i – 1] into 1 group).
return dp[K][n];
813 Length of Longest Fibonacci Subsequence
dp[i][j] = max length of sequence ends with A[i] and A[j]
Use a hashMap to save map from every element to its index int a_i = A[k] - A[j];// prune
if (a_i >= A[j]) // anti strictly increasing
break;
auto iter = hashMap.find(a_i);
if (iter == hashMap.end())
continue;
// find a fibonacci sequence, i,j,k
int i = iter->second;
dp[j][k] = dp[i][j] + 1; // dp formula
res = max(res, dp[j][k]);
474 Ones and Zeroes
For loop each str in strs independently do the following:
dp[i][j]: maximum strings can be formed by the using of i 0s and j 1s
Base Case: none
dp formula:
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
where i in [m, zeros], j in [n, ones]
673 Number of Longest Increasing Subsequence
Let len[i] denote the maximum length ending with nums[i], and cnt[i] denote the number of maximum length ending with nums[i], where i in [0, n - 1]
Base Case:
Initialize all len[i], and cnt[i] to 1, where i in [0, n - 1]
Under guard nums[i] > nums[j]
dp formula 1:
len[i] = len[j] + 1;
cnt[i] = cnt[j];
condition 1: when len[i] < len[j] + 1
dp formula 2:
len[i] = len[i];
cnt[i] += cnt[j]
condition 2: when len[i] = len[j] + 1
where i in [0, n - 1], j in [0, i - 1]
Also:
if (max_len == len[i]) {
res += cnt[i];
} else if (max_len < len[i]) {
max_len = len[i];
res = cnt[i];
}
return res;
| 698 |
Note this is similar to DFS problem 473 Matchsticks to Square. The partition problem is NP-Complete.
Base Case:
if (k <= 0 || sum % k != 0) return false
Call helper function: canPartition(nums, visited, 0, k, 0, sum / k);
bool canPartition(vector<int>& nums, vector<bool>& visited, int start_index, int k, int cur_sum, int target) {}
Base case for helper:
if (k == 1)
return true;
if (cur_sum == target) recursively call the helper with decreased k value by 1
return canPartition(nums, visited, 0 /*reset to 0*/, k - 1, 0, target);
Otherwise, for loop each number in the array, if not visited, mark it as visited and recursively call the helper canPartition with updated cur_sum and cur_num and increased start_index value. if any partition succeeds, return true. Otherwise, unmark the current num in the flag array and try next number.
O(2^N) DP solution
95 Unique Binary Search Trees II
dp[i][j] means the all the trees constructed from value i to j.
Base Case:
dp[i][i].push_back(new TreeNode(i));
DP formula:
for (int k = 1; k < n; k++) { // k is diff actually, len - 1
for (int i = 1; i <= n - k; i++) {
int j = i + k;
assert(dp[i][j].empty());
for (int root = i; root <= j; root++) {
int end_left = root - 1;
int start_right = root + 1;
Trees all_left;
if (end_left < i)
all_left.push_back(nullptr);
else
all_left = dp[i][end_left];
Trees all_right;
if (start_right > j)
all_right.push_back(nullptr);
else
all_right = dp[start_right][j];
for (const auto& left : all_left)
for (const auto& right : all_right) {
auto rootNode = new TreeNode(root);
rootNode->left = left;
rootNode->right = right;
dp[i][j].push_back(rootNode);
}
}
}
}
return dp[1][n];
790 Domino and Tromino Tiling
Base Case:dp[0] = 1; // dummy stub
dp[1] = 1;
dp[2] = 2;
DP Formula:
for (int i = 3; i <= N; i++) {
dp[i] = (2 * dp[i - 1] + dp[i - 3]) % M;
}
return dp[N];
where M = 1e9 + 7;
The key here is how you could figure out the dp formula
368 Largest Divisible Subset
DP formula:
dp[i] = max(dp[j] + 1) where j in [0, i - 1], under condition
nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1
pre[i] = j, whenever update dp[i], used to recover the result subset
264 Ugly Number II
Base Case:
int factor2 = 2;
int factor3 = 3;
int factor5 = 5;
DP Formula:
for (int i = 1; i < n; i++) {
dp[i] = min({factor2, factor3, factor5});
// how to update factor2/3/5
if (dp[i] == factor2)
factor2 = dp[++idx2] * 2;
if (dp[i] == factor3)
factor3 = dp[++idx3] * 3;
if (dp[i] == factor5)
factor5 = dp[++idx5] * 5;
}
return dp[n - 1];
808 Soup Servings
Base Case:
dp[i][j] means the probability that A finishes first with i ml A and j ml B.
dp[0][0] = 0.5; (tricky)
dp[0][j] = 1.0; for j in [1, n];
dp[i][0] = 0.0; for i in [1, n]
DP Formula:
dp[i][j] = 0.25 * (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] +
dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]);
return dp[n][n];
376 Wiggle Subsequence
DP formula:
if (nums[i] > nums[j])
up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])
down[i] = max(down[i], up[j] + 1);
where i in [1, n - 1], j in [0, i - 1]
return 1 + max(up[n - 1], down[n - 1]);
This can be further optimized to O(N) time and O(N) space DP.
Still define up[i] means the maximum wiggle sequence ending with a up curve
Here down[i] means the maximum wiggle sequence ending with a down curve
But we utilize the fact that up and down array are non-decreasing,
So that we can just compare nums[i] with nums[i - 1], also we know
up[i - 1] and down[i - 1] are the maximum value from up[0] - up[i - 1]
and down[0] - down[i - 1]
787 Cheapest Flights Within K Stops (Graph)
Note K stops, means K + 1 flights, allocate (K + 2)
Base Case:
dp[i][src] = 0; for any i in [0, K + 1]
for (int i = 1; i <= K + 1; i++) {
dp[i][src] = 0;
for (auto& flight : flights) {
auto& u = flight[0];
auto& v = flight[1];
auto& w = flight[2];
// DP formula:
dp[i][v] = min(dp[i][v], dp[i - 1][u] + w);
}
}
if (dp[K + 1][dst] == INT_MAX)
return -1;
return static_cast<int>(dp[K + 1][dst]);
=====================================================
Moving Around On Board
688 Knight Probability in Chessboard
Base Case:
dp[0][r][c] = 1.0;
DP formula:
dp[step][x][y] += dp[step - 1][i][j] * 0.125, where step in [1, K], i in [0, N), j in [0, N)
x, y is the next possible position the knight could get to from (i, j) in one step. Only update
these x, y that still within the board.
Base Case:
dp[0][r][c] = 1.0;
DP formula:
dp[step][x][y] += dp[step - 1][i][j] * 0.125, where step in [1, K], i in [0, N), j in [0, N)
x, y is the next possible position the knight could get to from (i, j) in one step. Only update
these x, y that still within the board.
576 Out of Boundary Paths
dp[k][i][j] means the total # of walk out of boundary at position [i][j] after walking k steps
vector<vector<vector<long> > > dp(N + 1, vector<vector<long> >(m, vector<long>(n, 0)));
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long fromTop = (i == 0 ? 1 : dp[k - 1][i - 1][j]);
long fromBottom = (i == m - 1 ? 1 : dp[k - 1][i + 1][j]);
long fromLeft = (j == 0 ? 1 : dp[k - 1][i][j - 1]);
long fromRight = (j == n - 1 ? 1 : dp[k - 1][i][j + 1]);
// DP formula:
dp[k][i][j] = (fromTop + fromBottom + fromLeft + fromRight) % M;
}
}
}
return static_cast<int>(dp[N][X][Y]);
=====================================================
| 221 |
dp[i][j] means the maximum side length ending with point [i][j]
Base Case:
dp[i][j] = matrix[i][j] - '0'; when i == 0 || j == 0
DP formula:
if (matrix[i][j] == '1')
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
801 Minimum Swaps To Make Sequences Increasing
Base Case:
swap[0] = 1;
keep[0] = 0;
DP Formula:
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
swap[i] = swap[i - 1] + 1; // swap both
keep[i] = keep[i - 1]; // no swap
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
swap[i] = min(swap[i], keep[i - 1] + 1); // swap ith not swap (i- 1) th pair
keep[i] = min(keep[i], swap[i - 1]); // not swap ith swap (i- 1) th pair
}
}
| 139 |
dp[i] means whether s.substr(0, i) could be constructed from the word dict
Base Case:
dp[0] = true; // so that the word can start with the first char
DP Formula:
dp[i] = Union{dp[j] && dict.count(s.substr(j, i - j)}, where (j >= 0 && j <= i - 1)
467 Unique Substrings in Wraparound String
dp[i] means the maximum sustring that ends with 'a' + i
for (int i = 0; i < p.size(); i++) {
if (i > 0 && ((p[i] + 26 - p[i - 1]) % 26 == 1))
len++;
else
len = 1;
// DP formula:
dp[p[i] - 'a'] = max(dp[p[i] - 'a'], len);
}
Get the total sum of dp[0] to dp[25] in the end.
898 Bitwise ORs of Subarrays
Here cur2 contains all the values could be constructed from the consecutive numbers ending with i ( i is the loop index)
int subarrayBitwiseORs(vector<int>& A) {
unordered_set<int> res, cur, cur2;
for (const auto& num1 : A) {
cur2 = {num1};
for (const auto& num2 : cur)
cur2.insert(num1 | num2);
cur = cur2;
for (const auto& num :cur)
res.insert(num);
}
return res.size();
}
| 322 |
Define dp[i] is the minimum number of coins used to change value i.
Base Case:
dp[0] = 0;
DP formula:
dp[i] = min(dp[i], dp[i - coins[j]] + 1) when i >= coins[j], where i in [1, amount], j in [0, coins.size() - 1]
| 837 |
Base Case
dp[0] = 1.0;
DP formula:
let MAX = K + W - 1
for (int i = 1; i <= MAX; i++)
for (int j = 1; j <= W; j++)
if (i - j >= 0 && i - j < K)
dp[i] += dp[i - j] / W;
return accumulate(dp[K], dp[K + 1] ... dp[N])
Optimization, Use prefix sum to avoid repeated calculation.
| 764 |
up[i][j] = i > 0 ? up[i - 1][j] + 1 : 1;
down[i][j] = i == N - 1 ? 1 : down[i + 1][j] + 1;
left[i][j] = j > 0 ? left[i][j - 1] + 1 : 1;
right[i][j] = j == N - 1 ? 1 : right[i][j + 1] + 1;
Under the condition that arr[i][j] != 0, otherwise all the up/down/left/right[i][j] equal zero
get a two-dimension result array with min of the 4 array in each position, then find the maximum in the array, which will be the result.
jtony
838 Push Dominoesleft to right
force = 0, if see 'L', force = N if see 'R', otherwise force = max(0, force - 1)
forces[i] += force,
Symmetrically, from right to left
force = 0, if see 'R', force = N if see 'L', otherwise force = max(0, force - 1)
forces[i] -= force,
In the end check whether forces[i] is > 0, == 0 or < 0, set them to 'R', 'L' '.' accordingly.
375 Guess Number Higher or Lower II
// dp[i][j]表示从数字i到j之间猜中任意一个数字最少需要花费的钱数
vector<vector<int> > dp(N + 1, vector<int>(N + 1, 0));
for (int i = 2; i <= N; i++) {
for (int j = i - 1; j >= 0; j--) {
int global_min = INT_MAX;
for (int k = j + 1; k < i; k++) {
int local_max = k + max(dp[j][k - 1], dp[k + 1][i]);
global_min = min(global_min, local_max);
}
dp[j][i] = i == j + 1 ? j : global_min; // Base case: j - i == 1, choose the smaller num
}
}
return dp[1][N];
Base Case:
dp[0][0] = 1; // // NOT 0!! so dp[1][1] = dp[0][0] * (N - 1 + 1) = 1 * N = N
DP formula:
dp[i][j] += dp[i - 1][j - 1] * (N - j + 1); // play a song for the first time
dp[i][j] += dp[i - 1][j] * max(0, j - K); // play a song played before
dp[i][j] %= M;
Intuition
Let dp[i][j] be the number of playlists of length i that have exactly j unique songs. We want dp[L][N], and it seems likely we can develop a recurrence for dp.
Algorithm
Consider dp[i][j]. Last song, we either played a song for the first time or we didn't. If we did, then we had dp[i-1][j-1] * (N-j + 1) ways to choose it. If we didn't, then we repeated a previous song in dp[i-1][j] * max(j-K, 0) ways (j of them, except the last K ones played are banned.)
Comments
Post a Comment