玩命加载中 . . .

121-买卖股票的最佳时机

动态规划
LeetCode
发布日期:   2021-12-18

LeetCode 121. Best Time to Buy and Sell Stock

LeetCode-121

You are given an array prices where prices[i] is the price of a given stock on the i^th^ day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

method 1: 贪心

因为只能持有一只股票，只要找到差值最大的两个数就行，当前价格必须比买入的价格高才行

int maxProfit(vector<int>& prices) {
    int low = INT_MAX;  // 记录最小数
    int res = 0;    // 最小数和当前元素的差值
    for (int i = 0; i < prices.size(); i++) {
        low = min(low, prices[i]);
        res = max(res, prices[i] - low);
    }
    return res;
}

method 2: 动态规划

dp[i][0]表示当前持有的股票，可以有两个来源

  • 当前不买入，持有跟之前一样，即dp[i-1][0]
  • 当前买入，即-prices[i]

dp[i][1]表示当前不持有的股票，也是两个来源

  • 之前就不持有，即dp[i-1][1]
  • 之前持有，现在卖出，所以是dp[i-1][0] + prices[i]

初始化，一开始就买入，dp[0][0] = -prices[0]，一开始没有卖出，所以dp[0][1] = 0

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2));
    dp[0][0] -= prices[0];
    for (int i = 1; i < prices.size(); i++) {
        dp[i][0] = max(dp[i - 1][0], -prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
    }
    return dp[n - 1][1];
}

只跟前一个状态有关，可以状态压缩

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(2, vector<int>(2));
    dp[0][0] -= prices[0];
    for (int i = 1; i < n; i++) {
        dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
        dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
    }
    return dp[(n - 1) % 2][1];
}

LeetCode 122. Best Time to Buy and Sell Stock II

LeetCode-122

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

method

跟上一题一样，只是可以多次买入卖出，所以当前持有的股票的利润来源要改成dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])，当前要买入，上一次就要卖出

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2));
    dp[0][0] = -prices[0];
    for (int i = 1; i < prices.size(); i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
    }
    return dp[n - 1][1];
}

同样可以用滚动数组

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(2, vector<int>(2));
    dp[0][0] = -prices[0];
    for (int i = 1; i < prices.size(); i++) {
        dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
        dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
    }
    return dp[(n - 1) % 2][1];
}

714. Best Time to Buy and Sell Stock with Transaction Fee

LeetCode-714

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

method

只是卖出的时候要减去手续费，其他都跟『题122』一样

int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2));
    dp[0][0] -= prices[0];
    for (int i = 1; i < prices.size(); i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return dp[n - 1][1];
}

LeetCode 123. Best Time to Buy and Sell Stock III

LeetCode-123

You are given an array prices where prices[i] is the price of a given stock on the i^th^ day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [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: prices = [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.

method

限制了只能两次买入卖出，定义5个状态

dp[i][0]表示不操作，所以等于dp[i - 1][0]
dp[i][1]表示考虑第一次买入，两个来源，保持原样或者买入
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
dp[i][2]表示考虑第一次卖出，两个来源，保持原样或者卖出
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]

同理，
dp[i][3]表示考虑第二次买入，两个来源，保持原样或者第一个卖出之后买入
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
dp[i][4]表示考虑第二次卖出，两个来源，保持原样或者第一次买入后卖出
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]

int maxProfit(vector<int>& prices) {
    vector<vector<int>> dp(prices.size(), vector<int>(5));
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];
    for (int i = 1; i < prices.size(); i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[dp.size() - 1][4];
}

LeetCode 188. Best Time to Buy and Sell Stock IV

LeetCode-188

You are given an integer array prices where prices[i] is the price of a given stock on the i^th^ day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
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.

method

dp[i][j]表示第i天状态为j时，所剩下的最大现金

  • 0表示不操作
  • 1表示第1次买入
  • 2表示第1次卖出
  • 3表示第2次买入
  • 4表示第2次卖出

所以除0外，奇数表示买入，偶数表示卖出，总共有2k+1个状态

int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0;
    vector<vector<int>> dp(n, vector<int>(2 * k + 1, 0));

    for (int j = 1; j < 2 * k; j += 2) {    // 奇数
        dp[0][j] = -prices[0];
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 2 * k; j += 2) {
            dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
            dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
        }
    }
    return dp[n - 1][2 * k];
}

LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

LeetCode-309

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

method

定义四种状态

  1. 保持买入
  2. 保持卖出
  3. 今天卖出
  4. 冷冻期

保持买入的来源有3个，要么前一天就是买入
dp[i][0] = dp[i-1][0]
要么前一天是保持卖出或者冷冻期，今天买入
dp[i][0] = max(dp[i-1][2], dp[i-1][3]) - prices[i]
3种取最大

保持卖出有2个来源，要么前一天就是卖出dp[i-1][1]
要么前一天是冷冻期dp[i-1][3]
2种取较大值：dp[i][1] = max(dp[i-1][1], dp[i-1][3])

今天要卖出，昨天只能是保持买入状态
dp[i][2] = dp[i-1][0] + prices[i]

今天是冷冻期，只能是昨天卖出，不能是昨天保持卖出，因为冷冻期只有一天
dp[i][3] = dp[i-1][2]

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(4));
    dp[0][0] = -prices[0];
    for (int i = 1; i < prices.size(); i++) {
        dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][3]) - prices[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][3]);
        dp[i][2] = dp[i-1][0] + prices[i];
        dp[i][3] = dp[i-1][2];
    }
    return max(dp[n-1][3], max(dp[n-1][1], dp[n-1][2]));
}
文章作者: kunpeng
文章链接: http://example.com/2021/12/18/LeetCode-121-%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 kunpeng !
动态规划
赏
  目录