股票交易最大利润问题:代码错误分析及修正
这段代码可能会出错的原因是在计算dp[i][t]时,使用了i%2来判断当前是奇数行还是偶数行,从而选择对应的状态转移方程。然而,这种判断方式是错误的。
在这段代码中,当t为奇数时,表示当前是买入股票的操作,而当t为偶数时,表示当前是卖出股票的操作。因此,在计算dp[i][t]时,应该根据t的奇偶性来选择对应的状态转移方程,而不是根据i的奇偶性。
正确的做法是使用一个变量来记录当前是买入还是卖出的操作。例如,可以使用一个变量isBuy来表示当前是否是买入操作,isBuy为true表示当前是买入操作,isBuy为false表示当前是卖出操作。根据isBuy的取值来选择对应的状态转移方程。
具体代码如下:
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
dp[0][0] = 0;
for (int i = 1; i <= 2 * k; i++) {
if (i % 2) {
dp[0][i] = -prices[0];
}
}
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = 0;
bool isBuy = true;
for (int t = 1; t < 2 * k + 1; t++) {
if (isBuy) {
dp[i][t] = max(dp[i - 1][t - 1] - prices[i], dp[i - 1][t]);
} else {
dp[i][t] = max(dp[i - 1][t - 1] + prices[i], dp[i - 1][t]);
}
isBuy = !isBuy;
}
}
return dp[prices.size() - 1][2 * k];
}
};
原文地址: https://www.cveoy.top/t/topic/qgnv 著作权归作者所有。请勿转载和采集!