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

发表于 分类于 阅读次数：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

解法1：动态规划

1.dp[i][k]表示第i天交易k次所能获得的最大利润

dp[i][k]有两种操作可以求出来，1.第i天什么都不做，那么dp[i][k]=dp[i-1][k].2.第i天选择卖出，既然选择了卖出，那么0-i-1天就要选择一天进行买入，且在买入前已经进行了k-1次交易。

我们用mins表示第1天到第i天prices[buy]-dp[buy][k-1]的最小值，（这样我们便能取得第i天卖出的最大利润）

然后比较dp[i-1][k]和prices[i]-mins，选择第i天到达进行什么操作

其中mins=min(mins,prices[i]-dp[i][k-1])

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0)
            return 0;
        vector<vector<int>> dp(n,vector<int>(3,0));
        for(int k=1;k<=2;k++)
        {
            int mins=prices[0];
            for(int i=1;i<n;i++)
            {
                mins=min(mins,prices[i]-dp[i][k-1]);
                dp[i][k]=max(dp[i-1][k],prices[i]-mins);
            }
        }
        return dp[n-1][2];
    }
};

解法2：优化时间复杂度

上面一种解法先将k放在外循环，i放在内循环，我们也可以对换位置，只要将mins赋对应初值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0)
            return 0;
        vector<int> dp(3,0);
        int mins[3];
        mins[0]=prices[0];
        mins[1]=prices[0];
        mins[2]=prices[0];
        for(int i=1;i<n;i++)
        {
            for(int k=1;k<=2;k++)
            {
                mins[k]=min(mins[k],prices[i]-dp[k-1]);
                dp[k]=max(dp[k],prices[i]-mins[k]);
            }
        }
        return dp[2];
    }
};

解法3：优化空间复杂度

上面的方法用了O（n）的空间复杂度，分析发现我们可以用O（1）的空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0)
            return 0;
        int min1=prices[0],min2=prices[0];
        int dp1=0,dp2=0;
        for(int i=1;i<n;i++)
        {
            min1=min(min1,prices[i]-0);
            dp1=max(dp1,prices[i]-min1);
            
            min2=min(min2,prices[i]-dp1);
            dp2=max(dp2,prices[i]-min2);
        }
        return dp2;
    }
};