【leetcode】188. 买卖股票的最佳时机4

题目内容

思路分析

本题是123. 买卖股票的最佳时机3 的更一般化，可直接由股票问题3的题解改编而来。

方法：动态规划

和股票问题3类似，使用一个大小为2k的数组cash来存储每一天的状态，令j为0,2,4,6...，则下标为j的元素代表某天买过j/2 + 1次，卖过j/2次；下标为j+1的元素代表某天买过j/2 + 1次，卖过j/2 + 1次。例如：

j	cash[j]含义	cash[j + 1]含义
0	买过1次，卖过0次	买过1次，卖过1次
2	买过2次，卖过1次	买过2次，卖过2次
4	买过3次，卖过2次	买过3次，卖过3次
j	买过j/2+1次，卖过j/2次	买过j/2+1次，卖过j/2+1次

因此可写出状态转移方程

// 买过j/2+1次，卖过j/2次 或 买过j/2次，卖过j/2次，当天又买了一次 -> 买过j/2+1次，卖过j/2次
if (j == 0) cash[j] = max(cash[j], - prices[i]);
if (j != 0) cash[j] = max(cash[j], cash[j - 1] - prices[i]);
// 买过j/2+1次，卖过j/2+1次 或 买过j/2+1次，卖过j/2次，当天又卖了一次 -> 买过j/2+1次，卖过j/2+1次
cash[j + 1] = max(cash[j + 1], cash[j] + prices[i]);

边界条件：

第一天时，最多买入一次，因此边界条件为：

cash[偶数] = -prices[0]  // 最多买一次，现金为负
cash[奇数] = 0  // 不买的话现金为0

另外有一个小细节是因为n天最多可进行n/2次交易，因此可k最多取n/2，可减小一定的时间复杂度和空间复杂度。

代码

#include <vector>

using namespace std;

class Solution {
public:
    // 动态规划
    // 时间复杂度O(n * min(n, k))，空间复杂度O(min(n, k))
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();

        if (n == 0 || n == 1 || k == 0) return 0;

        k = min(k, n / 2);  // n天最多进行n/2笔交易
        vector<int> cash(2 * k);  // 全0的vector

        // 边界条件
        // 第一天只能买不能卖且最多买一次
        for (int i = 0; i < 2 * k; i += 2) cash[i] = -prices[0];

        // 外层遍历股价
        for (int i = 1; i < n; ++i) {
            // 内层维护状态
            for (int j = 0; j < 2 * k; j += 2) {
                // 偶数表示买过j/2+1次，卖过j/2次
                // 买过j/2+1次，卖过j/2次 或 买过j/2次，卖过j/2次，当天又买了一次
                // -> 买过j/2+1次，卖过j/2次
                if (j == 0)
                    cash[j] = max(cash[j], - prices[i]);
                else
                    cash[j] = max(cash[j], cash[j - 1] - prices[i]);
                // 奇数表示买过j/2+1次，卖过j/2+1次
                // 买过j/2+1次，卖过j/2+1次 或 买过j/2+1次，卖过j/2次，当天又卖了一次
                // -> 买过j/2+1次，卖过j/2+1次
                cash[j + 1] = max(cash[j + 1], cash[j] + prices[i]);
            }         
        }

        return cash[2 * k - 1];
    }
};


int main() {
    Solution s;
    vector<int> input{ 3,2,6,5,0,3 };
    int k{ 2 };

    int output;
    output = s.maxProfit(k, input);

    return output;
}

收获

通用化了上一题的动态规划。