JLUVicent

123买卖股票的最佳时机III&188买卖股票的最佳时机IV

 
  • 2023年 04月05日
  • 0 阅读

day50

123.买卖股票的最佳时机III

题目链接：123. 买卖股票的最佳时机 III

解题思路：参考 视频

题目描述最多卖两次，因此可以理解为卖0次，卖1次，卖2次

1.确定dp数组及下标含义

  • 卖0次：$dp[i][0]$,相当于不操作
  • 卖1次：第一次持有股票：$dp[i][1]$；第一次不持有股票：$dp[i][2]$
  • 卖2次：第二次持有股票：$dp[i][3]$；第二次不持有股票：$dp[i][4]$

2.确定递推公式

$dp[i][0] = 0$，不操作数组一直为0

$dp[i][1]$：第一次持有股票的状态取决于第i-1次持有的状态，以及当前i次持有的状态取最大值

$dp[i][1] = max( dp[i-1][1],-prices[i] )$

$dp[i][2]$：第一次不持有股票的状态取决于第i-1次不持有的状态，以及当前i卖出股票取最大值

$dp[i][2] = max( dp[i-1][2],dp[i-1][1]+prices[i])$

$dp[i][3]$：第二次持有股票的状态取决于第i-1次持有的状态，以及当前i次持有股票的状态取最大值

当前i次持有股票的状态取决于上一次不持有股票的状态-当前的prices

$dp[i][3] = max( dp[i-1][3],dp[i-1][2]-prices[i])$

$dp[i][4]$：第二次不持有股票的状态取决于第i-1次不持有的状态，以及当前i次卖出股票的状态取最大值

$dp[i][4] = max( dp[i-1][4],dp[i-1][3]+prices[i] )$

3.初始化

dp[0][0] = 0;
dp[0][1] = -prices[0];	//在当前买入
dp[0][2] = 0;
dp[0][3] = -prices[0];	//这里第二次买入相当于第一天可以买卖多次
dp[0][4] = 0;

4.确定遍历顺序

后面状态取决于前面的状态，从前向后遍历

5.打印dp数组

看了前面的写这个题更好理解了

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //时间：O(n)
        //空间：O(n*5)
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(5));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];	//在当前买入
        dp[0][2] = 0;
        dp[0][3] = -prices[0];	//这里第二次买入相当于第一天可以买卖多次
        dp[0][4] = 0;
        for( int i = 1; i < n; i++){
            dp[i][0] = 0;
            dp[i][1] = max( dp[i-1][1], -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[n-1][4];
    }
};

优化空间的写法

// 版本二
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<int> dp(5, 0);
        dp[1] = -prices[0];
        dp[3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[1] = max(dp[1], dp[0] - prices[i]);
            dp[2] = max(dp[2], dp[1] + prices[i]);
            dp[3] = max(dp[3], dp[2] - prices[i]);
            dp[4] = max(dp[4], dp[3] + prices[i]);
        }
        return dp[4];
    }
};

188.买卖股票的最佳时机IV

题目链接：188. 买卖股票的最佳时机 IV

解题思路：参考 视频

本题第一次写根据之前的III的思路直接AC了

主要在于初始化和递推公式时候的不同

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(2*k+1));
        // 数组初始化 判断i是否为奇数，奇数就复制为-prices[0]
        for( int i = 0; i <= 2*k; i++){
            if( i % 2 == 1) dp[0][i] = -prices[0];
        }
        for( int i = 1; i < n; i++){
            for( int j = 1; j <= 2*k; j++){
                if( j % 2 == 1){
                    dp[i][j] = max( dp[i-1][j],dp[i-1][j-1] - prices[i]);
                }else{
                    dp[i][j] = max( dp[i-1][j],dp[i-1][j-1] + prices[i]);
                }
            }
        }
        return dp[n-1][2*k];
    }
};
搜索