力扣 122 买卖股票的最佳时机II
思路:
动态规划，表面上是\(O(2^n)\)的搜索空间，实际上该天的选择只与前一天的状态（是否持有股票）有关。从收益的角度来看，确实每一天的不同选择都会产生不同的分支。动态规划相当于对原解空间进行了剪枝，剪枝的关键在于之后的选择只与当前是否持有股票的状态有关，因此只需要保留当前状态下的最优值，就能保证最优解的保留。
对于这种时间序列或者类似的问题，可重点考虑其每一个阶段的状态。若考虑卖出，买入和保持，就很复杂，但是考虑是否持有就变成只有两个状态了。
本质上很像贪心，都能保证每一步的最优解。关键在于找到这个结构。
\(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])\)
class Solution {
public:
//动态规划
int maxProfit(vector<int>& prices) {
if(!prices.size()) return 0;
int n = prices.size();
int dp0 = 0;
int dp1 = -prices[0];
for(int i = 1; i < n; ++i){
dp0 = max(dp0,dp1 + prices[i]);
dp1 = max(dp0 - prices[i], dp1);
}
return max(dp0,dp1);
}
};
![2021-07-05：股票问题2。给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
![2021-07-07：股票问题4。给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成](https://www.kunjuke.com/file/css/thumb/9.jpg/280-180.jpg)
![[LeetCode] 122. 买卖股票的最佳时机ii best-time-to-buy-and-sell-stock-ii(贪心算法)](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
