买卖股票的最好时机(三)（动态规划）

题意

数值数组,最多两次买卖,两次买卖不重叠,问最大收益

思路分析

状态设计

主要有数组遍历下标和买卖状态

所以不妨设状态为[下标][买的次数][卖的次数]=当前最大收益

递推关系

注意到两次买卖不重叠,所以卖的次数+1>=买的次数>=卖的次数, 同时也可以知道,如果两个次数相等,最后一次发生的是卖,如果买次数更大,最后一次发生的是买

if(j == k){ // 卖
    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1] + prices[i]);
}else if(j > k){ // 买
    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] - prices[i]);
}

状态压缩

注意到递推关系,每次依赖于i-1的状态, 所以考虑循环利用空间把dp[i]改为dp[i%2].

而j,k不会超过3,可以考虑j+k*3进行编码

边界处理

下标来说(0-1)%2 == -1,因为(i+1)%2==(i-1)%2,所以把(i-1)%2改写成(i+1)%2省去边界判断

初始化时,0次购买收益为0, 而其它状态置为负无穷大-INF,

题目样例

以题目样例数据1为例,状态对应的值如图所示

最后输出0次,1次,2次买卖的最大值即可

题解

所以整合上面的内容

class Solution {
public:
    // 编码
    int enc(int buy,int sale){
        return buy + sale * 3;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0)return 0;
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> state = vector<vector<int>>(2,vector<int>(10,-INF));
        state[1][0] = 0; // 初始化
        for(int i = 0;i < n;i++){
            int v = prices[i]; // 价格
            for(int buy = 0;buy < 3;buy++){
                for(int sale = max(0,buy-1); sale <= buy ;sale++){
                    int j = enc(buy,sale);
                    state[i%2][j] = state[(i+1)%2][j];
                    // 当前是卖
                    if(sale > 0 && buy == sale){
                        state[i%2][j] = max(state[i%2][j], state[(i+1)%2][enc(buy,sale-1)] + v);
                    }
                    // 当前是买, 且次数大于卖
                    if(buy > sale){
                        state[i%2][j] = max(state[i%2][j], state[(i+1)%2][enc(buy-1,sale)] - v);
                    }
                }
            }
        }
        return max(0,max(state[(n-1)%2][enc(1,1)],state[(n-1)%2][enc(2,2)])); // 0次 1次 2次
    }
};

复杂度分析

空间复杂度: 存储状态数组大小为常数大小,所以空间复杂度为$O(1)O(1)$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为$O(n)O(n)$