原题
思路： 状态转移 出售股票的状态，最大利润有两种可能。 一，和昨天一样不动；二，昨天持有的股票今天卖掉。
sell[i] = max(sell[i-1],buy[i-1] + prices[i]);
购买股票的状态，最大利润有两种可能。 一，和昨天一样不动；二，两天前出售，今天购买。
bdp[i] = Math.max(bdp[i-1],sell[i-2] - prices[i]);
class Solution
{
public:
int maxProfit(vector<int> &prices)
{
if (prices.size() == 0)
return 0;
int len = prices.size();
vector<int> buy(len + 1, 0), sell(len + 1, 0);
buy[1] = -prices[0];
for (int i = 2; i <= len; i++)
{
buy[i] = max(buy[i - 1], sell[i - 2] - prices[i - 1]);
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i - 1]);
}
return sell[len];
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/9893444.html
