我花了大约3个小时来弄清楚这一点，但是我不了解两行代码：
b[j] = _max(b[j], s[j] - prices[i]);
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
以下代码是DP解决方案的问题是：买卖股票的最佳时间
说您有一个阵列，ITH元素是第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在做什么。
- 为什么我们要做
b[j] = _max(b[j], s[j] - prices[i]);的最大值，购买价格应该不是最低的？为什么B [J]这两件事的最大值？什么是s [j] - 价格[i]？ - 这可能与算法有关，但是为什么此陈述：
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);b [j] 价格[i]在此表达式中做什么，这是什么意思？ - 我们为什么要经历每天k时：
for (j = 0; j < k; j ++) {？
我花了很多时间(3个小时(思考该解决方案并将其与其他DP问题进行比较，但没有运气。我将其与最长增加的子序列DP问题进行了比较，以及您应该如何"让长度(k(表示最长增加的子序列的长度，该长度在K位置k"，并试图将该逻辑应用于此处的数组，但没有运气。
感谢您的任何帮助。
认为我们想将每个价格(或白天(视为购买日或销售日以达到最佳选择。b列表每天都将buy天视为s列表，为sell天。现在，我们只是实施逻辑。可能有点令人困惑的是，因为s在j + 1上更新，对于s列表，j是前一天。
最佳的k购买日以i的价格是我们已经拥有的k购买日，或者我们购买的是，这等于(k-1)最佳卖出日(这是s[j](自那以来就被买卖起来。我们刚买了！
b[j] = _max(b[j], s[j] - prices[i]);
最佳的k卖出日以i的价格是我们已经作为k卖出的日期或最好的k购买日(因为k The The Thar Thar既有买入又有卖出(加上今天的价格由于我们刚刚赚了出售股票！
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)