gpt4 book ai didi

c - 这个买卖股票的递归DP算法的算法和底层结构是什么?

转载 作者:太空狗 更新时间:2023-10-29 15:37:17 25 4
gpt4 key购买 nike

我花了大约 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 问题以及您应该如何“让长度 (k) 表示在位置 k 结束的最长递增子序列的长度”进行了比较,并尝试将该逻辑应用于此处的数组,但没有成功。

感谢您的帮助。

最佳答案

假设我们想将每个价格(或日期)视为买入日或卖出日,以得出最佳选择。 b 列表将每一天都视为buy 日,而s 列表将每一天视为sell 日。现在我们只是实现逻辑。可能有点令人困惑的是,因为 sj + 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]);

更新

根据 OP 的要求,这里有一个例子:[5, 20, 15, 100, 35] k = 2

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)

关于c - 这个买卖股票的递归DP算法的算法和底层结构是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57318811/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com