题目

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

题解

经典的 暴力递归 -> 傻缓存 -> DP，重要思路来源于之前做过的 leetcode 309. Best Time to Buy and Sell Stock with Cooldown | 309. 最佳买卖股票时机含冷冻期（动态规划）

当年看答案也摸不清门路的 dp，现在应不是玄学了，哈哈。

将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

没有草稿，直接上代码：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // Approach 1: Recursive, Brute Force
// return process1(prices, 0, false,fee);

        // Approach 2: Recursion with Memoization
// int[][] dp = new int[2][prices.length + 1];
// Arrays.fill(dp[0], Integer.MIN_VALUE);
// Arrays.fill(dp[1], Integer.MIN_VALUE);
// dp[0][prices.length] = 0;
// dp[1][prices.length] = 0;
// return process2(prices, 0, 0, fee, dp);

        // Approach 3: Dynamic Programming
        int[][] dp = new int[2][prices.length + 1];
        Arrays.fill(dp[0], Integer.MIN_VALUE);
        Arrays.fill(dp[1], Integer.MIN_VALUE);
        dp[0][prices.length] = 0;
        dp[1][prices.length] = 0;
        for (int i = prices.length - 1; i >= 0; i--) {
            for (int pending = 0; pending <= 1; pending++) {
                int p1 = Integer.MIN_VALUE;
                int p2 = Integer.MIN_VALUE;
                int p3 = Integer.MIN_VALUE;
                int p4 = Integer.MIN_VALUE;
                if (pending == 1) {
                    p1 = dp[1][i + 1]; // 不卖
                    p2 = dp[0][i + 1] + prices[i] - fee; // 卖
                } else {
                    p3 = dp[1][i + 1] - prices[i]; // 买
                    p4 = dp[0][i + 1]; // 不买
                }
                dp[pending][i] = Math.max(Math.max(p1, p2), Math.max(p3, p4));
            }
        }
        return dp[0][0];
    }

    // 从i位置开始做决策，获得的最大收益（pending表示当前是否持有股票）
// public int process1(int[] prices, int i, boolean pending, int fee) {
// if (i == prices.length) return 0;
//
// int p1 = Integer.MIN_VALUE;
// int p2 = Integer.MIN_VALUE;
// int p3 = Integer.MIN_VALUE;
// int p4 = Integer.MIN_VALUE;
// if (pending) {// 持有股票
// p1 = process1(prices, i + 1, true, fee); // 不卖
// p2 = process1(prices, i + 1, false, fee) + prices[i] - fee; // 卖
// } else { // 未持有股票
// p3 = process1(prices, i + 1, true, fee) - prices[i]; // 买
// p4 = process1(prices, i + 1, false, fee); // 不买
// }
// return Math.max(Math.max(p1, p2), Math.max(p3, p4));
// }

// public int process2(int[] prices, int i, int pending, int fee, int[][] dp) {
// if (dp[pending][i] != Integer.MIN_VALUE) return dp[pending][i];
//
// int p1 = Integer.MIN_VALUE;
// int p2 = Integer.MIN_VALUE;
// int p3 = Integer.MIN_VALUE;
// int p4 = Integer.MIN_VALUE;
// if (pending == 1) {// 持有股票
// p1 = process2(prices, i + 1, 1, fee, dp); // 不卖
// p2 = process2(prices, i + 1, 0, fee, dp) + prices[i] - fee; // 卖
// } else { // 未持有股票
// p3 = process2(prices, i + 1, 1, fee, dp) - prices[i]; // 买
// p4 = process2(prices, i + 1, 0, fee, dp); // 不买
// }
//
// int result = Math.max(Math.max(p1, p2), Math.max(p3, p4));
// dp[pending][i] = result;
// return result;
// }
}