121. 买卖股票的最佳时机
解题思路（股票系列通解）
1.dp含义：因为第i天的股票有两个状态，买和不买，那么就有两个维度
dp[i][0] 第i天持有这支股票的最大现金(不一定买) dp[i][1] 第i天不持有这支股票的最大现金(不一定卖)，（手上的钱）
2.递推公式
一直保持着持有这支股票的状态 dp[i-1][0]
买入这支股票 -prices[1]
dp[i][0] = max( dp[i-1][0] , -prices[1] );
不持有这支股票一直保持 dp[i-1][1]
如果在第i卖了这支股票 dp[i-1][0] + prices[i] 那么就是第i-1天持股时卖了，加上现金
dp[i][1] = max( dp[i-1][1] , dp[i-1][0] + prices[i] )
3.初始化
都是由前一天得出来的
dp[0][0] = -prices[0] 持股现金为股票钱
dp[0][0] = 0; 不持股现金为0
4.遍历顺序
从前往后
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
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], -prices[i]); //前者为之前某一天买了的现金，后面是当天买的现金
dp[i][1] = max( dp[i-1][1], dp[i-1][0] + prices[i]); //前者为一直保持不持股，后者为如果持股在这天卖了的现金
}
return dp[prices.size()-1][1]; //只需要返回不持股的状态，肯定比持股状态的钱多
}
};
122.买卖股票的最佳时机II
解题思路
这题当时是使用贪心算法解决的
而这次我们使用动态规划来做
这题卖出股票的思路不变，但是对于买入股票就有所区别了
dp[i][0] = max( dp[i-1][0], ) 前者是i-1持股，后者与买入股票1的区别就是，手头是第一次买，现金为0，而这题则是前一天不持股的现金(前面多次买卖的利润) - prices[1] (只能有一支股票)
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
dp[0][0] = -prices[0]; //持股，现金为第一天的价格
dp[0][1] = 0; //不持股，此时现金为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][1]; //不持股现金肯定最高
}
};时间复杂度：O（n）
空间复杂度：O（1）
收获
继续加油