这个递归DP算法买卖股票涉及到什么算法和基础结构？

Question

这个递归DP算法买卖股票涉及到什么算法和基础结构？

4

我花了大约3个小时来理解这段代码，但我无法理解其中两行：

b[j]     = _max(b[j],     s[j] - prices[i]);
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);

以下代码是针对以下问题的DP解决方案：股票买卖的最佳时机

假设你有一个数组，其中第i个元素是第i天给定股票的价格。

设计一种算法来找到最大利润。您可以完成至多k次交易。

注意：您不能同时进行多个交易（即在再次购买之前必须出售股票）。

示例1：输入：[2,4,1]，k = 2 输出：2 解释：在第1天买入（价格=2），在第2天卖出（价格=4），利润=4-2=2。

示例2：输入：[3,2,6,5,0,3]，k = 2 输出：7 解释：在第2天买入（价格=2），在第3天卖出（价格=6），利润=6-2=4。然后在第5天买入（价格=0），在第6天卖出（价格=3），利润=3-0=3。

int _max(int a, int b) {
    return a > b ? a : b;
}
int all_profits(int* prices, int pricesSize) {
    int i, d, p;

    p = 0;
    for (i = 1; i < pricesSize; i ++) {
        d = prices[i] - prices[i - 1];
        p = d > 0 ? p + d : p;  // get it as long as it is a profit!
    }

    return p;
}
int maxProfit(int k, int* prices, int pricesSize) {
    int *b, *s, *buff, i, j, p;

    if (pricesSize < 2) return 0;

    if (k >= pricesSize / 2) return all_profits(prices, pricesSize);

    buff = malloc((2 * k + 1) * sizeof(int));
    //assert(buff);
    b = &buff[0];
    s = &buff[k];

    for (i = 0; i < k; i ++) {
        b[i] = 0x80000000;  // min integer
        s[i] = 0;
    }
    s[k] = 0;

    for (i = 0; i < pricesSize; i ++) {
        for (j = 0; j < k; j ++) {
            // profit on buy is current buy or last sale minus today's price
            b[j]     = _max(b[j],     s[j] - prices[i]);
            // profit on sale is current sale or last buy plus today's price
            s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
        }
    }

    p = s[k];

    free(buff);

    return p;
}

我理解代码的全部内容，除了开头提到的两行代码：

buff数组的目的是什么？buff数组分为两部分，一部分包含b，另一部分包含s。据我所知，s[n]是您可以在第n天实现的最大利润。我不知道b在做什么。
为什么我们要做MAX of b[j] = _max(b[j], s[j] - prices[i]);，购买价格不应该是最低的吗？为什么b[j]是这两个数的最大值？s[j] - prices[i]是什么意思？
这可能也与算法有关，但为什么会有这个语句：s[j + 1] = _max(s[j + 1], b[j] + prices[i]); 这个表达式中的b[j] + prices[i]是干什么的，它的含义是什么？
为什么我们要经过每天k次循环：for (j = 0; j < k; j ++) {？

我花费了很多时间（3小时）思考这个解决方案并将其与其他DP问题进行比较，但没有成功。我将其与最长递增子序列DP问题进行比较，并尝试将该逻辑应用于这里的数组，但没有成功。

感谢您的任何帮助。

- herophant

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

考虑我们想把每个价格（或者日期）都视为“购买日”或“卖出日”来得出最佳选择。列表“b”将每天视为“购买日”，而列表“s”将每天视为“卖出日”。现在我们只需要实现这个逻辑。有点困惑的是，因为“s”在“j+1”处更新，对于列表“s”，“j”是前一天。

对于价格在i的第k个最佳购买日，要么是我们已经拥有的第k个最佳购买日，要么就是我们购买，也就是等于第(k-1)个最佳卖出日（那就是让人困惑的“s[j]”），减去购买价格，因为我们刚刚购买了！

b[j] = _max(b[j], s[j] - prices[i]);

对于第i天的股票价格而言，最佳的第k次卖出日是已知的第k次卖出日或者是最佳的第k次买入日（因为一笔第k次交易既包含了购买也包含了出售）加上今天的价格，因为我们刚刚通过出售股票赚到了这部分利润！

s[j + 1] = _max(s[j + 1], b[j] + prices[i]);

更新

根据提问者的要求，这里有一个例子：[5, 20, 15, 100, 35] k = 2。

最初的回答:

None (原回答为空)

b represents the most profit at
the jth buy considering prices up to i:
max(b[j], s[j] - prices[i])

s represents the most profit at
the jth sell (index j+1 in s) considering prices up to i:
max(s[j + 1], b[j] + prices[i])

note that when j = 0, s[j] (the sell before the first buy)
is always 0

prices[0]:
  j:  0     1
  b:  -5    -5 // max(-Inf, 0 - 5), max(-Inf, 0 - 5)
  s:  0     0  // max(0, -5 + 5), max(0, -5 + 5)

prices[1]:
  j:  0     1
  b:  -5    -5 // max(-5, 0 - 20), max(-5, 15 - 20)
  s:  15    15 // max(0, -5 + 20), max(0, -5 + 20)

prices[2]:
  j:  0    1
  b:  -5   0   // max(-5, 0 - 15), max(-5, 15 - 15)
  s:  15   15  // max(15, -5 + 15), max(15, 0 + 15)    

prices[3]:
  j:  0    1
  b:  -5   0   // max(-5, 0 - 100), max(0, 0 - 100) 
  s:  95   100 // max(15, -5 + 100), max(15, 0 + 100)

prices[4]:
  j:  0    1
  b:  -5   60  // max(-5, 0 - 35), max(0, 95 - 35)
  s:  95   100 // max(95, -5 + 35), max(100, 60 + 35)