【动态规划--买卖股票的最佳时期系列】

问题1：力扣问题链接
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0

动态规划5步曲

1.确定dp数组(dp table)以及下标含义。
  dp[i][0]表示第i天持有股票所得到的最多现金。
  注意“持有”不代表就是当天“买入”，也可能昨天就买入，今天没有卖出，保持“持有”状态。
  一开始的时候现金是0，加上第i天买入股票的现金就是-prices[i],是一个负数。
  dp[i][1]表示第i天不持有股票所得到的最多现金。
2.确定递推公式
  如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
 - 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
 - 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
   那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
   如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
 - 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
 - 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i -
   1][0]同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i -
   1][0]);
3.初始化dp数组
 - 由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i
 - 1][1], prices[i] + dp[i - 1][0]);可以看出
 - 其基础都是要从dp[0][0]和dp[0][1]推导出来。
 - 那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -=
   prices[0];
 - dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
4.确定遍历顺序
  从递推公式可以看出，dp[i]都是由dp[i-1]推导出来的，那么遍历顺序一定是从前向后。
5.举例推导dp数组
  以[7,1,5,3,6,4]为例，dp数组的状态如图所示：

dp[5][1]就是最终结果。

代码如下：

#include<iostream>
#include<vector>
using namespace std;
class Solution{
    
	public:
		int maxProfit(vector<int> &prices) {
    
			int len = prices.size();
			vector<vector<int>> dp(len,vector<int>(2));
			dp[0][0] = -prices[0];//dp[i][0]表示第i天持有股票所得的最多现金
			dp[0][1] = 0;//dp[i][1]表示第i天不持有股票所得的最多现金
			for (int i = 1; i < len; i++) {
    
				dp[i][0] = max(dp[i-1][0],-prices[i]);
				dp[i][1] = max(dp[i-1][1],dp[i][0]+prices[i]);
			}
			return dp[len-1][1];
		}
};
int main() {
    
	Solution Q;
	vector<int> price(6);
	for (int i = 0; i < 6; i++) {
    
		cin>>price[i];
	}
	cout<<Q.maxProfit(price);
}

问题2 力扣链接
题目和1相同，唯一不同的是股票可以买卖多次（注意只有一支股票，所以再次购买前出售之前的股票）
分析
本题和题目1唯一不同的地方就是推导dp[i][0]的时候，第i天买入股票的情况。
题目1中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有的股票即dp[i][0]就是-prices[i]。
在本题中一支股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能包含之前买卖股票所得到的利润。
那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]。
具体分析参考题目一的动规五步曲。
代码如下：

#include<iostream>
#include<vector>
using namespace std;
class Solution{
    
	public:
		int Maxprofit(vector<int> &prices) {
    
			vector<vector<int>> dp(prices.size(),vector<int>(2));
			dp[0][0] = -prices[0];
			dp[0][1] = 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] + dp[i-1][0]);
			}
			return dp[prices.size()-1][1];
		}
};