Day49_动态规划

32. 买卖股票的最佳时机

121. 买卖股票的最佳时机
思路一：

由于股票最多买入卖出一次，所以记录前面出现的最低股票价格，找到最低价格之后的最高价格出售，这里要注意统计的顺序，不要还没有买入就卖出了。

class Solution {
public:int maxProfit(vector<int>& prices) {int prices_size = prices.size();int low = INT_MAX;int result = 0;for (int i = 0; i < prices_size; i++) {low = min(low, prices[i]);result = max(result, prices[i] - low);}return result;}
};

思路二：

dp

dp[i][0]代表第i天手上不持股的最大持有现金数，
dp[i][1]代表第i天手上持股的最大持有现金数
递推公式：

dp[i][0] = max(dp[i-1][0], dp[i-1][0] + prices[i]); // max（前一天不持股，前一天持股但今天卖出去了）
dp[i][1] = max(-prices[i], dp[i-1][1]); // max(前一天不持股今天买入，前一天持股今天不卖出)

初始化：第一天买入或者不买入

dp[0][1] = -prices[0]
dp[0][0] = 0

递推顺序，每个dp[i-1]由其前一天递推而来，所以递归顺序从前往后
样例推演，偷图（不过图中的0和1与我的定义相反）

class Solution {
public:int maxProfit(vector<int>& prices) {int prices_size = prices.size();if (prices_size == 0) return 0;vector<vector<int>> dp(prices_size, vector<int>(2, 0));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices_size; i++) {dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = max(dp[i-1][1], -prices[i]);}return dp[prices_size - 1][0]; // 一定是不持股的现金多，持股手上现金数为负}
};

33. 买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II
思路

dp

dp[i][0]表示第i天不持股的现金数
dp[i][1]表示第i天持股的现金数
递推公式

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) // 前一天不持股今保持，前一天持股今日卖出
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]) // 前一天不持股今日买入，前一天持股今日保持

初始化：

dp[0][0] = 0
dp[0][1] = -prices[i]

递推顺序，从前往后

时间复杂度： $O (n)$
空间复杂度： $O (n)$

class Solution {
public:int maxProfit(vector<int>& prices) {int prices_size = prices.size();if (prices_size == 0) return 0;vector<vector<int>> dp(prices_size, vector<int>(2, 0));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices_size; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices_size - 1][0];}
};

利用滚动数组优化空间:
由于每天只用到了前一天的值，所以数组空间只需要开今天和昨天两天的维度大小即可

时间复杂度： $O (n)$
空间复杂度： $O (1)$

class Solution {
public:int maxProfit(vector<int>& prices) {int prices_size = prices.size();if (prices_size == 0) return 0;vector<vector<int>> dp(2, vector<int>(2, 0));dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < prices_size; i++) {dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] - prices[i]);}return dp[(prices_size - 1) % 2][0];}
};