摘要

• 有些动态规划的题目的难点在于如何划分状态和这些状态之间如何进行转移，列出可能的状态以及转移到这些状态的可能，是定义dp数组及数组下标、推导递推公式的关键。

• 画出简单的状态转移示意图，有助于清楚地划分状态以及模拟状态转移的过程，对如何定义dp数组以及推导状态转移方程有一定启发。

• 对于初始化中的非法状态，不要死抠dp数组的定义，只要初始值能让递推公式能正确计算即可。

• 有一部分可以使用动态规划解决的问题，如果问题具有贪心选择性质，也可以用贪心法解决，贪心法是动态规划的特例，贪心法的效率往往比动态规划要高。而动态规划往往是一类问题的通解，代码的复用性和可扩展性更好。

LeetCode309 最佳买卖股票的时机含冷冻期

309. 最佳买卖股票时机含冷冻期 - 力扣（Leetcode）

• 这道题目添加了“冷冻期”这个规则，需要更精细地划分每一天的状态。

  • 首先，本题不限制买卖股票地次数，所以不需要记录每天买卖股票的次数。但要先买入股票才能卖出股票，至少需要记录每天是否持有股票。

  • 但由于“冷冻期”的限制，不能再卖出股票后的第二天买入股票，所以卖出股票的第二天一定不能持有股票，这和其他时候没有持有股票的是不一样的。非“冷静期”时可以选择是否买入股票，而“冷静期”时不能选择买入股票。都是不持有股票，但应该区分冷静期和非冷静期。

  • 对一天的状态尝试进行划分，一天可能有如下4种状态

    1. 今天持有股票
    2. 今天卖出股票
    3. 今天是冷冻期，不能买入股票
    4. 今天不是冷冻期，且未持有股票

  • 然后要分析这些状态相互之间如何进行转移

    • 今天持有股票：
      1. 前一天持有股票且不卖出，那今天也是持有股票
      2. 前一天卖出了股票，今天是冷冻期，不能买入股票
      3. 前一天是冷冻期，那今天正好可以买入股票，今天买入股票
      4. 前一天不是冷冻期且未持有股票，那今天买入股票
    • 今天卖出股票
      1. 前一天一定要持有股票，今天才能卖出
    • 今天是冷冻期
      1. 只有前一天卖出了股票，今天才会是冷冻期
    • 今天不是冷冻期，且未持有股票
      1. 前一天是冷冻期，今天正好解冻，但是今天不买入股票
      2. 前一天不是冷冻期，也未持有股票，今天不买入股票

  • 可以得到这样的状态转移图

image.png

• 确定dp数组及数组下标的含义：dp[i][j]为到第i天时能获得的最大金额，j代表第i天处于什么状态：j==0为“今天持有股票”，j==1为“今天卖出股票”，j==2为“今天是冷静期”，j==3为“今天不是冷静期且未持有股票”。

• 确定状态转移方程，根据之前对状态转移的分析

  • 今天持有股票，dp[i][0]
    1. 前一天持有股票且不卖出，那今天也是持有股票
    2. 前一天卖出了股票，今天是冷冻期，不能买入股票，不能转移到这个状态
    3. 前一天是冷冻期，那今天正好可以买入股票，今天买入股票
    4. 前一天不是冷冻期且未持有股票，那今天买入股票
  • 今天卖出股票
    1. 前一天一定要持有股票，今天才能卖出
  • 今天是冷静期
    1. 只有前一天卖出了股票，今天才会是冷冻期
  • 今天不是冷静期且未持有股票
    1. 前一天是冷冻期，今天正好解冻，但是今天不买入股票
    2. 前一天不是冷冻期，也未持有股票，今天不买入股票

• 确定初始状态，初始化dp数组，假设初始金额为0

  • 第0天持有股票就是第0天买入，dp[0][0]=0-prices[i]
  • 第0天卖出股票，看成第0天买入再卖出（虽然题目不允许这样），也可以看成是为了要正确计算下一天处于冷静期时的dp值，dp[0][1]应该初始化成0。dp[0][1]=0
  • 第0天是冷静期，看成第0天买入再卖出，第0天也不允许再进行买卖了，也可以看成是为了要正确计算下一天未持有股票的dp值，dp[0][2]应该初始化成0。dp[0][2]=0
  • 第0天不是冷静期且未持有股票，实际上就是第0天什么也不做，dp[0][3]=0

• 每天的各个状态的更新都依赖于上一天的状态，所以i应该从小到大遍历。

题解代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
        dp[0][0] = 0 - prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;

        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][2], dp[i - 1][3]) - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = dp[i - 1][1];
            dp[i][3] = max(dp[i - 1][2], dp[i - 1][3]);
        }

        return max(dp[prices.size() - 1][1], max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));
    }
};

• 最后肯定是手上未持有股票时，持有的金额最大，而未持有股票实际上就对应着下标j为[1-3]的状态，从这三种中去最大值即可。

LeetCode714 买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费 - 力扣（Leetcode）

• 这道题目和 122. 买卖股票的最佳时机 II - 力扣（Leetcode） 也只是在递推公式上有区别，递推公式中需要加入手续费的计算。在 代码随想录算法训练营打卡Day49 中，已经用动态规划的思路较详细的分析了这道题，所以这次就简单的过一遍。

• dp数组及数组下标的含义：dp[i][j]表示到第i天时买卖股票能获得的最大利润，j==0表示当天持有股票，j==1当天未持有股票。

• 状态转移方程，假设初始金额为0

  • 对于第i天，

    • 如果持有股票，说明在第i天或之前的某一天买入了股票。
      • 如果是在第i天买入了股票，至少第i-1天时是未持有股票的，根据dp数组的定义，第i-1天持有的金额是dp[i-1][1]，那么第i天时持有的金额为；
      • 如果在之前的某一天买入了股票，现在还应该继续持有股票，所以 ，保持着持有之前买入的股票的状态。
    • 如果不持有股票，说明在第i天或之前的某一天卖出了股票。
      • 如果是在第i天买入了股票，至少第i-1天时是持有股票的，根据dp数组的定义，第i-1天持有的金额是dp[i-1][0]，然后不要忘记卖出股票时要支付手续费，那么第i天时持有的金额为；
      • 如果在之前的某一天卖出了股票，第i天还不应该买入股票，所以，保持之前的状态即可

• 初始化dp数组，第0天持有股票就是第0天买入股票，dp[0][0]=0-prices[i]；第0天未持有股票就是什么也不做，dp[0][0]=0。dp数组其他的值初始化成不影响递推公式计算结果的值即可，既然假设初始金额为0，那初始化成0就可以。

• 遍历顺序，就是今天的状态依赖上一天的状态，i从小到大遍历

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<vector<int>> dp(prices.size(), {0, 0});
        dp[0][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] - fee);
        }

        return dp[prices.size() - 1][1];
    }
};

• 似乎股票问题相当一部分能用贪心法解决，先写完这一轮的动态规划再回头看贪心法。