188.买卖股票的最佳时机IV
题目链接：188.买卖股票的最佳时机IV
文档讲解：代码随想录
状态：初始化情况没弄清
思路
类比买卖股票Ⅲ，次数增加到k次，显而易见的增加dp数组的维度即可。
在初始化时想当然的任务仅仅只有2个，最好列出二维dp数组看一下循环结构，看看哪一部分需要初始化。
题解
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));
//还是初始化问题
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for(int i = 1;i<prices.size();i++)
{
for(int j = 1;j<2*k;j+=2)
{
dp[i][j] = max(-prices[i]+dp[i-1][j-1],dp[i-1][j]);
dp[i][j+1] = max(prices[i]+dp[i-1][j],dp[i-1][j+1]);
}
}
return dp[prices.size()-1][2*k];
}
};
309.最佳买卖股票时机含冷冻期
题目链接：309.最佳买卖股票时机含冷冻期
文档讲解：代码随想录
状态：不会，脑子不清晰
思路
最难的股票题目来啦：难点在于如何将冷却期这个状态合理地添加进入动态规划中。
解决方法，先从基本的情况入手，用文字（其意义）代表状态列一下递归方程，看看需要什么单独的状态，就添加什么状态。
动手列，有意义的列，最好不要直接写代码，不然dp数组含义容易混乱。
题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(3,0));
dp[0][0] = -prices[0];
//剩下两个是0不用初始化。
for(int i= 1;i<prices.size();i++)
{
dp[i][0] = max(-prices[i]+dp[i-1][2],dp[i-1][0]);
dp[i][1] = dp[i-1][0]+prices[i];
dp[i][2] = max(dp[i-1][2],dp[i-1][1]);
}
return max(dp[prices.size()-1][1],dp[prices.size()-1][2]);
}
};
714.买卖股票的最佳时机含手续费
题目链接：714.买卖股票的最佳时机含手续费
文档讲解：代码随想录
状态：轻松AC
思路
与股票问题Ⅱ类似，无限次购买股票，但是有了手续费。
价值问题而非状态问题，很好解决。
题解
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
dp[0][0] = -prices[0]-fee;
dp[0][1] = 0;
for(int i = 1;i<prices.size();i++)
{
dp[i][0] = max(dp[i-1][1]-fee-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];
}
};
股票问题总结
所有的股票问题如下：
其主要思路是动态规划，对于简单的问题特定情况下可用贪心解决。
解决问题的方式无非是使用dp描述所有状态，或者说正确全部的递推所需要的所有状态。
几个新的或者思考点：
dp数组含义明确，是每天结束的最后一刻，不要陷入当天买卖的漩涡。- 初始化（尤其多维
dp）要看遍历情况初始化，不能随便代值。 - 还是
dp数组含义，一定搞清楚后文字表述清楚再列递推公式。