买卖股票的最好时机(四)

题目描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

  1. 你最多可以对该股票有k笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
  2. 如果不能获取收益，请返回0
  3. 假设买入卖出均无手续费

方法一：动态规划方法

解题思路

对于本题目的求解，利用动态规划的思想，首先我们用dp[i][j][k]表示前i天交易次数为j时的状态。然后我们有状态转移方程：

dp[i][j][0]=max(dp[i−1][j][0],dp[i−1][j][1]+prices[i−1]);dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);

dp[i][j][1]=max(dp[i−1][j][1],dp[i−1][j−1][0]−prices[i−1]);dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);

根据上面的转移方程，即可求出本题的答案。

alt

解题代码

class Solution {
public:
    int dp[1005][105][2]={0};
    int maxProfit(vector<int>& prices, int k) {
        int n=prices.size();
        k=min(k,n/2);
        for(int j=1;j<=k;j++){
            dp[1][j][1]=-prices[0];
        }
        
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){//状态转移方程
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
                dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
            }
        }
        return dp[n][k][0];
    }
};

复杂度分析

时间复杂度：时间复杂度为O(Nk)O(Nk)，其中N为天数，k为最大交易次数。

空间复杂度：空间复杂度为O(Nk)O(Nk)，其中N为天数，k为最大交易次数。

方法二：二维代替三维方法

解题思路

基于方法一，我们可以用两个二维数组来代替方法一中的三维数组中的第三维。

解题代码

class Solution {
public:

    int a[1005][105]={0};
    int b[1005][105]={0};
    int maxProfit(vector<int>& prices, int k) {
        int n=prices.size();
        k=min(k,n/2);
    
        for(int j=1;j<=k;j++){
            b[1][j]=-prices[0];
        }
        
        for(int i=2;i<=n;i++){
            for(int j=1;j<=k;j++){//状态转移方程
                a[i][j]=max(a[i-1][j],b[i-1][j]+prices[i-1]);
                b[i][j]=max(b[i-1][j],a[i-1][j-1]-prices[i-1]);
            }
        }
        return a[n][k];
    }
};

复杂度分析

时间复杂度：时间复杂度为O(Nk)O(Nk)，其中N为天数，k为最大交易次数。

空间复杂度：空间复杂度为O(Nk)O(Nk)，其中N为天数，k为最大交易次数。