买卖股票的最佳时机 IV

Category Difficulty Likes Dislikes
algorithms Hard (42.25%) 806 -
Tags

Companies

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

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

示例 1：

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

示例 2：

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

提示：

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

动态规划(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem188.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=188 lang=cpp
 *
 * [188] 买卖股票的最佳时机 IV
 */

/** 
 * 3 2 6 5 0 3
 * n = prices.size()
 * 只卖一次：i = (1 ~ n-1) f[0][1] = -prices[0]; 
 * f[i][0] = max(f[i-1][0], -prices[i]);
 * f[i][1] = max(f[i-1][0], f[i-1][1]) + -prices[i] > 0 ? 
 * 
 * 3 2 6 5 0 3

 * -3 -2 -2 -2 0 0
 * 0 0 4 4 4 4 
 * -3 -3 -2 -1 4 4
 * 0 0 4 4 4 7
 * 
 * 2 4 1 
 * -2 -2 -1
 * 0 2 2 
 * -2 -2 1 
 * 0 2 2  
 * 
 * k次 f[k][n][2];
 * 边界：f[(1~k)][0][0] = -prices[0]; f[(0~k)][0][1] = 0;
 * f[(1~k)][(1~n)][0] = max(f[(1-k)-1][(1~n)[1]]-prices[(1~n)], f[(i-k)-1][(1~n)-1][0]);
 * f[1~k][1~n][1] = max(f[1~k][1~n][0] + prices[1~n], f[1~k][(1~n)-1][1]);
 */

// @lc code=start
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<vector<int>>> f(k+1, vector<vector<int>>(n, vector<int>(2, 0)));
        for (int i = 1; i <= k; ++i) {
            f[i][0][0] = -prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < k + 1; ++j) {
                f[j][i][0] = max(f[j - 1][i][1] - prices[i], f[j][i - 1][0]);
                f[j][i][1] = max(f[j][i][0] + prices[i], f[j][i - 1][1]);
            }
        }t.
        return f[k][n - 1][1];
    }
};
// @lc code=end