问题描述
解题思路
本题的关键在于找到dp
的实际含义,以及它的递推关系;
dp[i]
表示只考虑前i
天的情况,那么到了第i
天,有五种可能的情况:
- 没有做任何操作,记为
dp[i][0]
; - 前
i
天发生了一次买入,记为dp[i][1]
:dp[i][1] = max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1])
- 前
i
天发生了一次卖出,记为dp[i][2]
:dp[i][2] = max(dp[i - 1][1] + prices[i - 1], dp[i - 1][2])
- 前
i
天发生了两次买入,记为dp[i][3]
:dp[i][3] = max(dp[i - 1][2] - prices[i - 1], dp[i - 1][3])
- 前
i
天发生了两次卖出,记为dp[i][4]
:dp[i][4] = max(dp[i - 1][3] + prices[i - 1], dp[i - 1][4])
初始化:
dp[0][0] = 0;
dp[0][1] = -prices[0];
// 发生了一次买入dp[0][2] = 0;
// 买入又卖出dp[0][3] = -prices[0];
// 买入->卖出->买入dp[0][4] = 0;
// 买入->卖出->买入->卖出
代码
#include <vector>
using std::vector;
class Solution {
public:
int maxProfit(vector<int> &prices) {
vector<vector<int>> dp(prices.size() + 1, vector<int>(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i <= prices.size(); i++) {
dp[i][1] = max(dp[i - 1][0] - prices[i - 1], dp[i - 1][1]);
dp[i][2] = max(dp[i - 1][1] + prices[i - 1], dp[i - 1][2]);
dp[i][3] = max(dp[i - 1][2] - prices[i - 1], dp[i - 1][3]);
dp[i][4] = max(dp[i - 1][3] + prices[i - 1], dp[i - 1][4]);
}
return dp[prices.size()][4];
}
};
标签:sell,buy,记为,max,vector,123,买入,prices,dp
From: https://www.cnblogs.com/zwyyy456/p/16792263.html