以下问题在没有进行状态压缩前，都是套用一个模板分析的状态转移、写出的代码，因此面试的时候可以直接先把没有进行状态压缩的算法写出来，再在此基础上修改代码优化空间。

---

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

// 状态量： 
//     天数 & 是否持有股票
// dp[i][j]定义：
//     第i天手里有或没有股票的最大利润；
// 状态转移：
//     第i天持有股票：dp[i][1]
//         可能是第i-1天以前就买过了 dp[i][1] = dp[i-1][1]
//         也可能是第i天刚买入的 dp[i][1] = dp[i-1][0] - prices[i]
//     第i天不持有股票：dp[i][0]
//         可能是i-1天持有股票，i天刚好卖出；dp[i][0] = dp[i-1][1] + prices[i]
//         也可能是i-1天就没有股票； dp[i][0] = dp[i-1][0]
// 初始状态：
//     dp[0][0] = 0
//     dp[0][1] = - prices[0]
// 返回值：
//     最后一天不持有股票的最大利润，即：dp[prices.length - 1][0]

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][1] = - prices[0];
        for (int i = 1; i < prices.length; ++i) {
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
            dp[i][0] = Math.max(dp[i-1][1] + prices[i], dp[i-1][0]);
        }
        return dp[prices.length - 1][0];
    }
}

空间压缩：观察到第i天是否持有股票只由i-1天决定，因此不需要记录再久之间的状态。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        '''
        状态转移：
        第i天持有股票，state1
            可能是i-1天以前买的： 
            也可能是i天刚买的
        第i天不持有股票，state0
            可能是i-1天以前卖的，
            也可能是第i天刚卖的 

        '''
        # state0 代表当前不持有股票的最大收益， state1 代表当前持有股票的最大收益
        state0, state1 = 0, -prices[0]
        for i in range(1, len(prices)):
            state0_new = max(state0, state1 + prices[i])
            state1_new = max(state1, state0 - prices[i])
            state0, state1 = state0_new, state1_new
        return max(state0, state1)

贪心策略：由于可以无限次交易，我们只需要记录当前的增量并将其累加就可，而得到的结果就是最终的全局最优解。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            tmp = prices[i] - prices[i - 1]
            if tmp > 0: profit += tmp
        return profit

---

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

'''题解：DP
dp数组的含义：
    dp[i][j]代表当前第i天在状态j时的最大收益
状态：
    第i天持有股票: dp[i][0]，第i天没有股票: dp[i][1]
状态转移：
    1. 第i天持有股票：
        可能是第i-1天持有的股票：dp[i-1][0]
        也可能是第i天刚买的股票：dp[i-1][1] - prices[i]
        state1 = max(dp[i-1][0], dp[i-1][1] - prices[i])
    2. 第i天不持有股票：
        可能是第i-1天就没有股票：dp[i-1][1]
        也可能是第i天刚卖出股票：dp[i-1][0] + prices[i] - fee
        state2 = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
边界条件：
    dp[0][0] = -prices[0]
    dp[0][1] = 0
最终输出：
    res = max(dp[n-1][0],dp[n-1][1])
空间优化：
    state1, state2 = -prices[0], 0
复杂度分析：
    T(n) = O(n); S(n) = O(1)
'''
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        prices_len = len(prices)
        if prices_len == 0 or prices_len == 1: return 0
        state1, state2 = -prices[0], 0
        for i in range(1, prices_len):
            state1_new = max(state1, state2 - prices[i])
            state2_new = max(state2, state1 + prices[i] - fee)
            state1, state2 = state1_new, state2_new
        return max(state1, state2)

贪心解法：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len=prices.length;
        if (len<2){
            return 0;
        }
        int res=0,min=prices[0];
        for (int i = 1; i <len ; i++) {
            if (prices[i]<min){
                //未发生买卖时找到第一个最小数，如果发生过买卖则比较当前价格和上次卖出时的价格减去手续费
                min=prices[i];
            }else {
                if (prices[i]-fee>min){
                    res+=prices[i]-min-fee;
                    //当前的价格已经减过手续费，所以min的值应为当前价格减去手续费。
                    min=prices[i]-fee;
                }
            }
        }
        return res;
    }
}

---

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

// 状态量：
//     天数 & 是否持有股票 & 是否处于冷冻期
// dp定义：
//     dp[i][j][k] 为第i天后持有/不持有股票处于/不处于冷冻期的最大收益；
//     不持有不处于均用0表示，持有处于均用1表示；
// 状态转移：
//     第i天后持有股票：
//         可能是第i-1天已经持有的：dp[i][1][0] = dp[i-1][1][0]
//         也可能是第i天刚好买入的：dp[i][1][0] = dp[i-1][0][0] - prices[i]
//     第i天后不持有股票：
//         第i-1天后就没持有股票
//             此时可能是i-1天本来就没有股票：dp[i][0][0] = dp[i-1][0][0]
//             也可能是i-1天刚好卖出，此时i-1天后处于冷冻期：dp[i][0][0] = dp[i-1][0][1]
//         第i天刚卖出，此时第i-1天持有股票，第i天后处于冷冻期：dp[i][0][1] = dp[i-1][1][0] + prices[i]
// 初始化：
//     dp[0][0][k] = 0
//     dp[0][1][k] = - prices[0]

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int[][][] dp = new int[prices.length][2][2];
        for (int k = 0; k < 2; ++k) {
            dp[0][1][k] = -prices[0];
        }
        for (int i = 1; i < prices.length; ++i) {
            dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][0][0] - prices[i]);
            dp[i][0][0] = Math.max(dp[i-1][0][0], dp[i-1][0][1]);
            dp[i][0][1] = dp[i-1][1][0] + prices[i];
        }
        Arrays.sort(dp[prices.length - 1][0]);
        return dp[prices.length - 1][0][1];
    }
}

空间压缩：观察到冷冻期只会出现在前一天刚卖完，当前这一天才会处在冷冻期，因此可以将状态量减小为三个。

'''题解：DP
状态：
    1. 当前第i天持有股票：dp[i][0]
    2. 当前第i天不持有股票，处于冷冻期（第i天刚卖出股票）：dp[i][1]
    3. 当前第i天不持有股票，不处于冷冻期（第i天没有卖出股票）：dp[i][2]
dp数组含义：
    dp[i][j]代表第i天j状态下的最大收益
状态转移：
    1. 第i天持有的股票可能是第i-1天已经持有的：dp[i-1][0]
       也可能是第i天刚好买入的（此时i-1天只有不处在冷冻期第i天才能买入）：dp[i-1][2]
        dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
    2. 第i天刚卖出股票意味着i-1天一定持有股票：
        dp[i][1] = dp[i-1][0] + prices[i]
    3. 第i天不持有股票且当天没有卖出股票：
        dp[i][2] = max(dp[i-1][1], dp[i-1][2])
边界条件：
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    dp[0][2] = 0
最终结果：
    n = len(prices)
    res = max(dp[n-1][0], dp[n-1][1], dp[n-1][2])
空间优化：
    第i天状态只由i-1天状态决定，因此可以用三个变量分别记录i-1天时三个状态的最大收益：
    状态1: state1_stock
    状态2: state2_selling
    状态3: state3_selled
'''
from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        prices_len = len(prices)
        if prices_len == 0 or prices_len == 1: return 0
        state1, state2, state3 = -prices[0], 0, 0
        for i in range(prices_len):
            state1_new = max(state1, state3 - prices[i])
            state2_new = state1 + prices[i]
            state3_new = max(state2, state3)
            state1, state2, state3 = state1_new, state2_new, state3_new
        return max(state1, state2, state3)

sol = Solution()
prices = [1,2,3,0,2]
print(sol.maxProfit(prices))

---

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

// 状态量：
//     天数 & 是否持有股票 & 已完成的交易数
// dp数组定义：
//     dp[i][j][k] 第i天后持有或不持有股票完成k笔交易的最大利润；
//     i 与prices[]下标一致
//     j = 0 -> 不持有 j = 1 -> 持有
//     k = 0, 1, 2
// 状态转移：
//     第i天后持有股票：
//         可能是第i-1天也持有股票：dp[i][1][k] = dp[i-1][1][k]
//         也可能是第i天刚买入股票：dp[i][1][k] = dp[i-1][0][k] - prices[i]
//     第i天后不持有股票：
//         可能是第i-1天也不持有股票：dp[i][0][k] = dp[i-1][0][k]
//         也可能是第i天刚卖出股票，此时相较于i-1天，完成的交易数+1：dp[i][0][k] = dp[i-1][1][k-1] + prices[i]
// 初始化：
//     dp[0][0][k] = 0
//     dp[0][1][k] = - prices[0]
// 返回：
//     最后一天后完成0，1，2笔交易后不持有股票的最大值。
class Solution {
    public int maxProfit(int[] prices) {
        int[][][] dp = new int[prices.length][2][3];
        for (int k = 0; k < 3; ++k) {
            dp[0][1][k] = -prices[0];
        }
        for (int i = 1; i < prices.length; ++i) {
            for (int k = 0; k < 3; ++k) {
                dp[i][1][k] = Math.max(dp[i-1][1][k], dp[i-1][0][k] - prices[i]);
            }
            for (int k = 1; k < 3; ++k) {
                dp[i][0][k] = Math.max(dp[i-1][0][k], dp[i-1][1][k-1] + prices[i]);
            }
        }
        Arrays.sort(dp[prices.length-1][0]);
        return dp[prices.length-1][0][2];
    }
}

空间压缩：参考地址

---

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

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;
        int[][][] dp = new int[prices.length][2][k+1];
        for (int count = 0; count < k+1; ++count) {
            dp[0][1][count] = -prices[0];
        }
        for (int i = 1; i < prices.length; ++i) {
            for (int count = 0; count < k+1; ++count) {
                dp[i][1][count] = Math.max(dp[i-1][1][count], dp[i-1][0][count] - prices[i]);
            }
            for (int count = 1; count < k+1; ++count) {
                dp[i][0][count] = Math.max(dp[i-1][0][count], dp[i-1][1][count-1] + prices[i]);
            }
        }
        Arrays.sort(dp[prices.length-1][0]);
        return dp[prices.length-1][0][k];
    }
}