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

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

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

动态规划

相较于 123.买卖股票的最佳时机III，此处对于交易的次数进行了另一种限定，交易的次数是可变的。尝试依旧采取同样的方式去定义动态规划数组：

1. 动态规划数组的定义：定义数组 dp[i][2*k+1] ，分别表示在第 i 天的 2*k+1 种状态

• dp[i][0] 表示在第 i 天未对股票进行任何操作所拥有的最大现金数
• dp[i][1] 表示在第 i 天第一次持有股票所拥有的最大现金数
• dp[i][2] 表示在第 i 天第一次不持有股票所拥有的最大现金数
• …

1. 动态规划数组的推导：推导的方式依旧是是从前一天进行推导。

• dp[i][1] 表示在第 i 天第一次持有股票所拥有的最大现金数，那么只有前一天就持有和前一天不持有两种情况： dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
• dp[i][2] 表示在第 i 天第一次不持有股票所拥有的最大现金数，那么只有前一天持有和前一天不持有两种情况： dp[i][2]=max(dp[i-1][1]+prices[i],dp[i-1][2])
• • dp[i][3] 表示在第 i 天第二次持有股票所拥有的最大现金数，那么只有前一天就持有和前一天不持有两种情况： dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])
• dp[i][4] 表示在第 i 天第二次不持有股票所拥有的最大现金数，那么只有前一天持有和前一天不持有两种情况： dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4])
• …

1. 动态规划数组的初始化：对于第 0 天情形，不操作股票现金为0： dp[0][0]=0 。第 2i+1 次持有就是在当天买入 dp[0][2i+1]=-prices[0] 第 2i 次持有就是在当天卖出 dp[0][2i]=0
2. 动态规划数组的遍历：对于当前状态的推导需要使用前一天的数据，从前向后遍历。
3. 举例验证：对于 k = 2, prices = [2,4,1] ，求解的过程为：

dp={0,-2, 0,-2, 0}
dp={0,-2, 2,-2, 2}
dp={0, 0, 0, 0, 0}
dp={0,-2, 0,-2, 0}
dp={0,-2, 2,-2, 2}
dp={0,-1, 2, 1, 2}

代码实现：为了优化空间复杂度，此处采取滚动数组的方式实现

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<=1) return 0;
        int d=2*k+1;
        vector<vector<int>> dp(2,vector<int>(d,0));
        for(int i=1;i<d;i+=2){
            dp[0][i]-=prices[0];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<d;j++){
                if(j%2){ // 奇数
                    dp[1][j]=max(dp[0][j],dp[0][j-1]-prices[i]);
                }else{
                    dp[1][j]=max(dp[0][j-1]+prices[i],dp[0][j]);
                }
            }
            dp[0]=dp[1];
        }
        return dp[1][d-1];
    }
};