代码随想录算法训练营第36期DAY52
...
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<int> dp(2 * k + 1, 0);
// 别忘了初始化:
for (int j = 1; j < 2 * k; j += 2) {
dp[j] = -prices[0];
}
//初始化错了,应该是price[0],为什么呢:因为它是在第一天,用的第一天来初始化。
/* 错误:
for (int i = 1; i < 2 * k; i += 2) {
if (i % 2 != 0)
dp[i] = -1 * prices[i];
}
*/
for (int i = 0; i < prices.size(); i++) {
for (int j = 1; j <= 2 * k; j++) {
if (j % 2 != 0)
dp[j] = max(dp[j], dp[j - 1] - prices[i]);
else
dp[j] = max(dp[j], dp[j - 1] + prices[i]);
}
}
return dp[2 * k];
}
};