121.买卖股票的最佳时机
题目链接：121.买卖股票的最佳时机
文档讲解：代码随想录
状态：不会，股票状态表示不会
思路
普通解法：保存最小值，逐个做差取最大，怪不得是简单题，模拟就可以。
动态规划：后面还有一大堆股票问题来袭，得用动态规划呀。
关键在dp数组的含义了，dp数组表示状态，买卖股票有什么状态？到了第几个股票肯定有一个[i]，持有还是不持有也算一个（这个是整体的状态，至于为啥这样定义，咱也不敢问啊，反正定义是否持有[i]远不行）。
好简单，好简单的就成为了股神
题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
// int low = INT_MAX, result = 0;
// for(int i = 0;i<prices.size();i++)
// {
// low = min(low,prices[i]);
// result = max(result,prices[i]-low);
// }
// return result;
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(-prices[i],dp[i-1][0]);
dp[i][1] = max(prices[i]+dp[i-1][0],dp[i-1][1]);
}
return dp[prices.size()-1][1];
}
};
122.买卖股票的最佳时机II
题目链接：122.买卖股票的最佳时机II
文档讲解：代码随想录
状态：在同一天买卖卡住了
思路
与上一题相比，买卖次数不限制。
记得贪心算法吗，这个题给的启示：1->3->5买了就买与留到最后是一样的，可以贪心。
动态规划算法，与上题基本类似，关键点在于递归公式中要看看之前为0的情况需要加上值，因为不知道之前进行过几次购买了。
动态规划不要考虑当天买卖，无意义也不符合动态规划的本质。
题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
// int res = 0;
// for(int i = 1;i<prices.size();i++)
// {
// if(prices[i]-prices[i-1]>0)res +=prices[i]-prices[i-1];
// }
// return res;
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][1]-prices[i],dp[i-1][0]);
//dp[i][1] = max(prices[i]+dp[i-1][0],prices[i]+dp[i-1][1],dp[i-1][1]);
dp[i][1] = max(prices[i]+dp[i-1][0],dp[i-1][1]);
}
return dp[prices.size()-1][1];
}
};
123.买卖股票的最佳时机III
题目链接：123.买卖股票的最佳时机III
文档讲解：代码随想录
状态：初始化差一步，差一步AC困难
思路
多了一个状态：第一次or第二次，而原来只有一次。
关键点在于初始化，用到的都要看看，这个题目最难的是想到dp[0][2]初始化。
小tips：可以把三维数组状态简化一下，感觉更方便操作。
题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(4,0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = -prices[0];
dp[0][3] = 0;
for(int i = 1;i<prices.size();i++)
{
dp[i][0] = max(-prices[i],dp[i-1][0]);
dp[i][1] = max(prices[i]+dp[i-1][0],dp[i-1][1]);
dp[i][2] = max(dp[i-1][1]-prices[i],dp[i-1][2]);
dp[i][3] = max(prices[i]+dp[i-1][2],dp[i-1][3]);
}
return dp[prices.size()-1][3];
}
};