基本题目

198. 打家劫舍

类似子序和问题，添加限制——不能紧挨着选：`dp[i] = max(dp[i-2] + nums[i], dp[i-1])

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        int a = 0, b = nums[0], tmp;
        for (int i = 1; i < n; i++) {
            tmp = max(a + nums[i], b);
            a = b;
            b = tmp;
        }
        return b;
    }
};

213. 打家劫舍 II

唯一新增的约束：首尾元素无法同时选择。分别去掉首尾元素，计算各自最大值

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];

        int a = 0, b = nums[0], tmp;
        for (int i = 1; i < n - 1; i++) {
            tmp = max(a + nums[i], b);
            a = b;
            b = tmp;
        }

        int c = 0, d = nums[1];
        for (int i = 2; i < n; i++) {
            tmp = max(c + nums[i], d);
            c = d;
            d = tmp;
        }

        return max(b, d);
    }
};

337. 打家劫舍 III

备忘录，分别处理是否选择当前节点的情况

class Solution {
public:
    unordered_map<TreeNode *, int> select;
    unordered_map<TreeNode *, int> skip;

    int rob(TreeNode* root) {
        return max(rob(root, true), rob(root, false));
    }

    int rob(TreeNode* root, bool selected) {
        if (!root) return 0;
        if (selected) {
            if (select.count(root)) return select[root];
            select[root] = root->val + rob(root->left, false) + rob(root->right, false);
            return select[root];
        }
        else {
            if (skip.count(root)) return skip[root];
            skip[root] = rob(root->left) + rob(root->right);
            return skip[root];
        }
    }
};

一个节点的返回数值仅取决于其孩子节点的数值，因此可以调整计算顺序，规避使用备忘录

class Solution {
public:
    int rob(TreeNode* root) {
        pair<int, int> &&result = solve(root);
        return max(result.first, result.second);
    }

    pair<int, int> solve(TreeNode* root) {
        if (!root) return {0, 0};
        pair<int, int> &&left = solve(root->left);
        pair<int, int> &&right = solve(root->right);
        int selected = root->val + left.second + right.second;
        int skipped = max(left.first, left.second) + max(right.first, right.second);
        return {selected, skipped};
    }
};

121. 买卖股票的最佳时机

动态规划：维护当前天数之前的最小值（缩减为单个数值）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int minVal = prices[0], maxProf = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] < minVal) minVal = prices[i];
            else if (prices[i] - minVal > maxProf) maxProf = prices[i] - minVal;
        }
        return maxProf;
    }
};

122. 买卖股票的最佳时机 II

动态规划思想：每一支股票的持有时间都划分为长度为 1 的小区间（今天买明天必须卖，但可以马上再买），dp[i] = max(dp[i-1], dp[i-1] + diff)（昨天卖后是否当天再买）

还可以采用贪心思想：每一支股票可以当天卖出，也可以持到第二天，这取决于上涨还是下跌

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 1) return 0;
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1])
                sum += (prices[i] - prices[i - 1]);
        }
        return sum;
    }
};

123. 买卖股票的最佳时机 III

每一天结束时，总共可能有 5 个状态：已卖出 0/1/2 支，持有第 1/2 支。将它们分别表示为 sold0, sold1, sold2, hold0, hold1，按状态变化的顺序排列为 sold0, hold0, sold1, hold1, sold2，则 sold2[i] = max(sold2[i-1], hold1[i-1] + prices[i])，hold1[i] = max(hold1[i-1], sold1[i-1] - prices[i])，其他同理，只依赖于前一天的数值

注意到，由于初始值 sold1 设置为 0，最终更新 sold2 时不仅仅会考虑恰好买卖两次的情况，还会考虑不足两次的情形。因此无需再找不同次数的最大值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int hold0 = -1e9, hold1 = -1e9, sold1 = 0, sold2 = 0;
        for (const int &price : prices) {
            sold2 = max(sold2, hold1 + price);
            hold1 = max(hold1, sold1 - price);
            sold1 = max(sold1, hold0 + price);
            hold0 = max(hold0, -price);
        }
        return sold2;
    }
};

188. 买卖股票的最佳时机 IV

基于 123 题的拓展，将重复部分用循环替代

注意 k 的优化，减少循环次数：最多交易次数为总天数的一半

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        k = min((int)prices.size() / 2, k);
        vector<int> hold(k, INT_MIN), sold(k + 1, 0);
        for (const int &price : prices) {
            for (int i = k - 1; i >= 0; i--) {
                sold[i + 1] = max(sold[i + 1], hold[i] + price);
                hold[i] = max(hold[i], sold[i] - price);
            }
        }
        return sold[k];
    }
};

309. 最佳买卖股票时机含冷冻期

基于前几题的扩展，需要微调 hold 转移方程

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sold_penult = 0, sold = 0, hold = INT_MIN, tmp;
        for (const int &price : prices) {
            tmp = sold;
            sold = max(sold, hold + price);
            hold = max(hold, sold_penult - price);
            sold_penult = tmp;
        }
        return sold;
    }
};

对比 122 题，为什么当时不需要维护任何的 dp 数组？这是因为按这种方式定义的 hold 和 sold 的状态转移方程是完全对称的，可以合并为一个数组，而它也可以使用滚动方式优化

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

与上一题类似，需要微调 hold 转移方程

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int sold = 0, hold = INT_MIN, tmp;
        for (const int &price : prices) {
            tmp = sold;
            sold = max(sold, hold + price);
            hold = max(hold, tmp - price - fee);
        }
        return sold;
    }
};

本题也可使用贪心思想。先引入手续费：在买入时必须支付手续费，但如果当天卖出了前一支股票，那么再买时可以免去手续费。后寻找购买时机：记录股票的购买金额（包含手续费），遍历数组，如果当天的购买金额更低，则用它替换之前的购买金额；如果当天卖出价格高于购买金额，则直接选择卖出，并将购买金额调整为当前股票的金额（不含手续费）

正确性证明：按上述方法得到的持有股票的时间段，若存在两个区间相邻，那么合并前后的总收入是不变的，手续费的差异被抵消了。另一方面，在遍历的过程中，算法做的比较实际上就是判断是要持有上一支股票到当天（和购买金额比较），还是宁可从当天买新的股票。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int sum = 0;
        int buy_price = INT_MAX;
        for (const int &price : prices) {
            if (price + fee < buy_price) buy_price = price + fee;
            else if (price > buy_price) {
                sum += price - buy_price;
                buy_price = price;
            }
        }
        return sum;
    }
};