题目1：121 买卖股票的最佳时机
题目链接：买卖股票的最佳时机
对题目的理解
prices[i]表示一支股票在第i天的价格，只能在某一天买入这支股票，并在之后的某一天卖出该股票，从而获得最大利润，返回该最大值，若不能获取利润，则返回0
注意：股票只能买卖一次
暴力解法(超时)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result=0;
for(int i=0;i<prices.size();i++){
for(int j=i+1;j<prices.size();j++){
result=max(result,prices[j]-prices[i]);
}
}
return result;
}
};- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
贪心解法
股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result=0;
int low=INT_MAX;
for(int i=0;i<prices.size();i++){
low=min(low,prices[i]);
result=max(result,prices[i]-low);
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
动态规划
动规五部曲
1）dp数组及下标i的含义（使用二维dp数组）
dp[i][0]表示第i天持有这支股票所拥有的最大现金，注意是持有，不一定是当天买入，可能是前天已经买入
dp[i][1]表示第i天不持有这支股票所拥有的最大现金，注意是持有，不一定是当天卖出，可能是前天已经卖出
最终求 dp[prices.size()][1]
本题中不持有股票状态所得金钱一定比持有股票状态得到的多
2）递推公式
dp[i][0] = dp[i-1][0] 一直持有该股票
dp[i][0] = -prices[i] 在第i天买入这支股票，减去股票的价格，因为只买卖一次，所以直接等于-princes[i]
dp[i][0]=max(dp[i-1][0], -prices[i])
dp[i][1] = dp[i-1][1] 一直不持有该股票
dp[i][1] = dp[i-1][0] + prices[i] 在第i天将这支股票卖了，那么前一天一定是持有这只股票,所以是二者相加
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
3）dp数组初始化
根据递推公式，dp[i]由dp[i-1]推出来，由前一个状态推出来
所以初始化，最前面的状态 第0天持有这支股票的最大现金(买入)：dp[0][0]=-prices[0]
第1天不持有这支股票的状态(没有股票，不买入)：dp[0][1]=0
4）遍历顺序
根据递推公式，后面状态依赖于前面的状态，所以从前往后进行遍历
for(int i=1;i<prices.size();i++){}
5）打印dp数组
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
//dp数组定义
vector<vector<int>> dp(prices.size(),vector<int>(2));
//初始化dp数组
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];
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
题目2：122 买卖股票的最佳时机Ⅱ
题目链接：买卖股票的最佳时机Ⅱ
对题目的理解
prices[i]表示某支股票的第i天的价格，在每一天，都可以决定买入或者卖出股票，但是每天最多只能持有1支股票，可先购买，在同一天出售，返回获得的最大利润
可以多次买卖股票
贪心解法（利润分解）
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]，相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
把利润分解为每天为单位的维度，只收集每天的正利润，注意至少要第2天才会有正利润
局部最优：收集每天的正利润，全局最优：求得最大利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for(int i=1;i<prices.size();i++){
result += max(0,prices[i]-prices[i-1]);//收集正利润
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i][0] ：第i天持有股票的最大现金
dp[i][1]：第i天不持有股票的最大现金
2）递推公式
dp[i][0] = dp[i-1][0] ：一直不持有股票
dp[i][0] = dp[i-1][1] - prices[i] 在第i天买入股票，因为题目中描述可以多次买卖股票，所以使用第i-1天不持有股票的最大现金减去股票的价格
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])
dp[i][1] = dp[i-1][1] : 一直不持有股票
dp[i][1] = dp[i-1][0] + prices[i] 在第i天卖出股票，说明第i-1天一定持有股票
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
3）dp数组初始化
根据递推公式，后面的状态由前面的状态推导出来的，所以初始化dp[0][0]和dp[0][1]
dp[0][0]=-prices[0]
dp[0][1]=0
4）遍历顺序
根据递推公式，后面状态由前面状态推导,所以从前向后遍历
for(i=1;i<prices.size();i++) 注意这里是从1开始遍历的，因为i的状态，取决于i-1的状态
5）打印dp数组
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
//定义dp数组
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
//初始化dp数组
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],dp[i-1][0]+prices[i]);
}
return dp[prices.size()-1][1];
}
};- 时间复杂度：O(n)
- 空间复杂度：O(n)
