代码随想录——动态规划、股票问题

https://www.programmercarl.com/动态规划-股票问题总结篇.html#买卖股票的最佳时机含手续费

只能买一次

不断更新最小买入值，不断更新profit=prices[i]-buy

可以买卖多次

动态规划

- 定义dp数组
dp[i][1],dp[i][0]分别表示第i天持有股票时的现金和第i天未持有股票时的现金
- 递推公式
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
要么延续前一天相同状态，要么买/卖当前股票
- 初始化
dp[i]需要dp[i-1]，因此初始化dp[0]。
dp[0][0]表示第0天没有股票的现金——0
dp[0][1]表示第0天持有股票的现金——为计算正确令为-prices[0]
- 遍历顺序
从前往后遍历

最多买卖两次

动态规划

一天一共就有五个状态，

• 没有操作
• 第一次买入
• 第一次卖出
• 第二次买入
• 第二次卖出
  dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(5,0));
        //dp[i][j],i是第i天，j从0-4表示四种状态下持有的现金
        dp[0][0] = 0;//0还没有买过
        dp[0][1] = -prices[0];//1第一次买入股票状态
        dp[0][2] = 0;//2第一次卖掉股票状态
        dp[0][3] = -prices[0];//3第二次买入股票状态
        dp[0][4] = 0;//第二次卖出
        for(int i=1;i<n;i++){
            dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]);
            dp[i][2] = max(dp[i-1][2],dp[i-1][1] + prices[i]);
            dp[i][3] = max(dp[i-1][3],dp[i-1][2] - prices[i]);
            dp[i][4] = max(dp[i-1][4],dp[i-1][3] + prices[i]);
        }
        // 利润最大一定是卖出股票的状态。而dp[i][4]可以=dp[i][2]所以返回4
        return dp[n-1][4];
    }
};

最多买卖k次

动态规划

规律：除了0以外，偶数就是卖出，奇数就是买入。
题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。

• 所以二维dp数组的C++定义为：
  vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
• 初始化
  在初始化的地方同样要类比j为偶数是卖、奇数是买的状态。

买卖多次，卖出有一天冷冻期

动态规划

具体可以区分出如下四个状态：

• 状态一：今天持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
• 不持有股票状态，这里就有两种卖出股票状态
  • 状态二：今天保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
  • 状态三：今天卖出股票
• 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
  

「今天卖出股票」我是没有单独列出一个状态的归类为「不持有股票的状态」，而本题为什么要单独列出「今天卖出股票」 一个状态呢？

因为本题我们有冷冻期，而冷冻期的前一天，只能是 「今天卖出股票」状态，如果是 「不持有股票状态」那么就很模糊，因为不一定是 卖出股票的操作。

初始化

dp数组如何初始化
这里主要讨论一下第0天如何初始化。

如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，一定是当天买入股票。

保持卖出股票状态（状态二），这里其实从 「状态二」的定义来说 ，很难明确应该初始多少，这种情况我们就看递推公式需要我们给他初始成什么数值。

如果i为1，第1天买入股票，那么递归公式中需要计算 dp[i - 1][1] - prices[i] ，即 dp[0][1] - prices[1]，那么大家感受一下 dp[0][1] （即第0天的状态二）应该初始成多少，只能初始为0。想一想如果初始为其他数值，是我们第1天买入股票后 手里还剩的现金数量是不是就不对了。

今天卖出了股票（状态三），同上分析，dp[0][2]初始化为0，dp[0][3]也初始为0。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(5,0));
        //1持有股票 2当天卖 3保持卖出 4冷冻期
        //之前定义0从未买过股票是因为买股票次数有限，现在不限则不需要定义。可以当天买当天卖。
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++){
            dp[i][1] = max(dp[i-1][4] - prices[i],max(dp[i-1][1],dp[i-1][3] - prices[i]));
            dp[i][2] = dp[i-1][1] + prices[i];
            dp[i][3] = max(dp[i-1][3],dp[i-1][4]);
            dp[i][4] = dp[i-1][2];
        }
        return max(dp[n-1][2],max(dp[n-1][3],dp[n-1][4]));
    }
};

有手续费

卖的时候扣手续费即可