LeetCode Best Time to Buy and Sell Stock with Cooldown
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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
又是股票买卖问题。在LeetCode Best Time to Buy and Sell Stock II的基础上，限制一次交易之后必须冷却一天，隔天才能再次买入。此时就不能再用贪心策略了，还需要用DP。参考这篇博客解法I。
定义两个数组sells和buys，sells[i]表示第i天的动作是卖出，截止当前的最大收益；buys[i]表示第i天的动作是买入，截止当前的最大收益。显然buys[0]=–prices[0], sells[0]=0。
令profit=prices[i]-prices[i-1]，递推公式如下：
Say you have an array for which the i-th 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).
Example 1:
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
第二个公式就好理解了，前i天最多交易j次的全局最大收益为“最后一次交易不在第i天发生，则globalBest[i-1][j]”与“最后一次交易在第i天发生，则mustSell[i][j]”的较大者。 如果允许交易的次数k很大，那么以上DP效率较低，可以换成LeetCode Best Time to Buy and Sell Stock II的贪心策略。因为一次交易至少涉及到两天，所以如果k>=prices.size()/2时，可以采用贪心策略。
完整代码如下：
class Solution {
public:
int maxProfit(int k, vector<int>& prices)
{
int days = prices.size();
if (days < 2)
return 0;
if (k >= days / 2) {
int ans = 0;
for (int i = 1; i < days; ++i) {
if (prices[i] > prices[i – 1])
ans += (prices[i] – prices[i – 1]);
}
return ans;
}
vector<vector<int> > mustSell(days, vector<int>(k + 1, 0)), globalBest(days, vector<int>(k + 1, 0));
for (int i = 1; i < days; ++i) {
int profit = prices[i] – prices[i – 1];
for (int j = 1; j <= k; ++j) {
mustSell[i][j] = max(globalBest[i – 1][j – 1] + profit, mustSell[i – 1][j] + profit);
globalBest[i][j] = max(globalBest[i – 1][j], mustSell[i][j]);
}
}
return globalBest[days – 1][k];
}
};
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 (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
股票买卖题三。这次限制最多交易两次，问最大能获利多少。这确实是个hard题，研一卜神算法作业中遇到过。 先来回顾一下股票买卖第一题LeetCode Best Time to Buy and Sell Stock，当时的做法是从左往右找到除了当前值的最小值min_so_far，然后用当前值减去min_so_far，表示如果在当前卖出（即用min_so_far买入）能获得的最大收益profit1。这一题允许最多两次交易，那么如果求到在当前买入能获得的最大收益profit2，则profit1+profit2表示在当前卖出后买入能获得的最大收益。计算所有的profit1+profit2的最大值，就是两次交易能获得的最大收益。 计算profit2的方法和计算profit1类似，此时我们从右往左找到除了当前值的最大值max_so_far，则用max_so_far减去当前值，就表示在当前买入（max_so_far卖出）能获得的最大收益profit2。
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
LeetCode Arithmetic Slices
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Note:m and n will be at most 100.
Example 1:
Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
