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

发表于 分类于 阅读次数： Waline： 本文字数： 124 阅读时长 ≈ 1 分钟

考点

  • 状态机DP

思路

与123. 买卖股票的最佳时机 III的思路完全一致，可以见该篇题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e3 + 5, neg = 0xcfcfcfcf;
    int maxProfit(int K, vector<int>& prices) {
        int f[205][2], n = prices.size();
        for (int i = 0; i <= K << 1; ++i)
            f[i][0] = 0, f[i][1] = neg;
        for (int i = 1; i <= n; ++i) {
            for (int k = 2 * K; k >= 1; --k) {
                f[k][0] = max(f[k][0], f[k - 1][1] + prices[i - 1]);
                f[k][1] = max(f[k][1], f[k - 1][0] - prices[i - 1]);
            }
        }
        return f[2 * K][0];
    }
};