带手续费买卖股票的最大利益[找DP的状态定义到底缺什么？]

前言

贪心考察逻辑分析能力 & 抽象问题能力，动态规划也是一样，如何将问题转化为更小规模但性质相同的问题，真的很考察抽象问题能力，不抽象出来，给人的感觉就是有无数种复杂的可能，无法着手做题！

一、带手续的买卖股票

二、贪心 & DP + 贪心

1、贪心

// 买股票的最佳时机。
public class MaxProfit {
    
    /* 贪心点：先手持该支股票，因为卖掉股票需要花费手续费fee，所以手持股票的价格就是买入价格 + fee. 当碰到价格比这个高的时候就卖了，赚钱，但是后面可能价格更高，局部拿不到最优解，那就把此时卖掉的价格当成过度价格，后面更高的价格就直接取差价当收益。 当碰到比手持股票价格 - fee 还低的时机时，拿肯定不要前面买那一次，毕竟到这个低点时都赚不到钱，不如手持这个更低的股票价格。 当碰到比手持股票价格低，但有比手持股票价格 - fee高，则不管，毕竟卖了不仅是不赚钱，还要亏钱。 注：相当于把问题转换为手续费为0的卖股票，当且仅当买股票时把手续费先算上，就0手续费 + 不做亏钱买卖。 贪心最考察抽象能力：其实什么时候买和卖不重要，重要的是最大利益是多少。 */
    public int maxProfit(int[] prices, int fee) {
    
        int buy = prices[0] + fee;
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
    
            if (prices[i] + fee < buy) {
    
                buy = prices[i] + fee;
            } else if (prices[i] > buy) {
    
                profit += prices[i] - buy;
                // 后面的不要手续。
                buy = prices[i];
            }
            // 继续寻找可以卖的时机。
        }
        return profit;
    }
}

2、DP + 贪心

// 一题多解，动态规划 + 贪心，将大问题转换为相同性能但规模更小的子问题递进。
class MaxProfit2 {
    
    // 以天为时间线，最后一天不持有股票的收益 为 max(前一天不持有股票,前一天持有股票今天卖了)(贪心体现)
    public int maxProfit(int[] prices, int fee) {
    
        int n = prices.length;
        int[][] f = new int[n][2];//1-状态定义

        f[0][1] = -prices[0];//2-初始化
        for (int i = 1; i < n; i++) {
    
            //3-状态转移
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i] - fee);
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
        }
        return f[n - 1][0];//4-最终状态
    }
    // 状压
    public int maxProfit2(int[] prices, int fee) {
    
        int n = prices.length;
        int[] f = new int[2];

        f[1] = -prices[0];
        for (int i = 1; i < n; i++) {
    
            int old = f[0];

            f[0] = Math.max(old, f[1] + prices[i] - fee);
            f[1] = Math.max(f[1], old - prices[i]);
        }
        return f[0];
    }
    /* review: 1-为什么我知道DP是应用在大问题分解相同性质小规模问题上，也知道DP四要素（状态定义/状态递进/初始状态/最终状态），却想不到状态的定义，或者说无法将问题抽象出来。 A)DP做少了无题感； B)没有抓住关键线--循环线，DP一般为一层/两层/三层循环来改变状态，那么循环就得有条循环线，如按时间，如该题按天数，第i天。 一个len = n的数组，要求到达最后一天的收益，是否可以先求前n-1的收益？ */
}

总结

1）贪心/DP真的很考察问题抽象能力，不抽象会感觉到问题的模拟复杂性。
2）抽象就要抓主干问题是什么，其他不需要的信息不要携带。
3）知道DP是应用在大问题分解相同性质小规模问题上，也知道DP四要素（状态定义/状态递进/初始状态/最终状态），却想不到状态的定义，或者说无法将问题抽象出来？
A)DP做少了无题感；
B)没有抓住关键线–循环线，DP一般为一层/两层/三层循环来改变状态，那么循环就得有条循环线，如按时间，如该题按天数，第i天。
4）DP的状态含义就是问题所求，如该题的最大利益；而DP数组的每个变量所在位置，则表示该最大利益发生在什么时候。总结：什么时候 & 什么状态。

参考文献

[1] LeetCode 买卖股票的最佳时机含手续费