终是谁使弦断
花落肩头
恍惚迷离
C++，动态规划。
看评论区和题解，好像是有很多道类似的股票题，但这是我碰到的第一道，这种题一看就是dp，但最惨的是不知道怎么去推导和确定关系。
看了评论区和题解区的大佬题解，慢慢就懂了点了。
可以说是简单dp+状态机。
两种状态：
- 持有股票
- 不持有股票
一个dp数组对应一种状态，也就是用hold_dp数组记录当天持有股票的最大利润，用unhold_dp数组记录当天不持有股票的最大利润。
持有股票状态：
- 昨天持有，今天继续持有，对应就是
hold_dp[i] = hold_dp[i-1] - 前天卖掉了，今天买回来，对应就是
hold_dp[i] = unhold_dp[i-2] - prices[i]
不持有股票状态：
- 昨天持有，今天卖掉了，对应就是
unhold_dp[i] = hold_dp[i-1] + prices[i] - 昨天不持有，今天继续不持有
unhold_dp[i] = unhold_dp[i-1]
于是就能写出代码了。
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
if (n <= 1) return 0;
vector<int> hold_dp(n);
vector<int> unhold_dp = hold_dp;
hold_dp[0] = -prices[0];
hold_dp[1] = max(hold_dp[0], -prices[1]);
unhold_dp[0] = 0;
unhold_dp[1] = max(0, prices[1] - prices[0]);
for (int i = 2; i < n; i++) {
hold_dp[i] = max(unhold_dp[i-2] - prices[i], hold_dp[i-1]);
unhold_dp[i] = max(hold[i-1] + prices[i], unhold_dp[i-1]);
}
return max(hold_dp[n-1], unhold_dp[n-1]);
}
};
仔细想想就会发现，把hold和unhold定义为数组是不合理的，既然只是与i与i-1或者i-2之间的关系，就可以用临时变量去替代数组。
使用O(1)空间：
class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
if (n <= 1) return 0;
int hold_pre = -prices[0];
int hold = max(hold_pre, -prices[1]);
int unhold_pre = 0;
int unhold = max(0, prices[1] - prices[0]);
for (int i = 2; i < n; i++) {
hold_pre = hold;
hold = max(unhold_pre - prices[i], hold);
unhold_pre = unhold;
unhold = max(hold_pre + prices[i], unhold);
}
return max(hold, unhold);
}
};
