代码随想录刷题|LeetCode 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费

目录

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

思路

1、确定dp数组以及下标含义

2、确定递推公式

3、初始化

 4、遍历顺序

5、获取结果

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

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

思路

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

---

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

题目链接：力扣

思路

1、确定dp数组以及下标含义

dp[i][j] 表示：第 i 天状态为 j , 手中的最大现金数位 dp[i][j]

这道题目就是状态不好分清

状态分析：

• 状态一：持有股票（今天刚买入持有股票，或者是之前就买入了股票然后没有进行操作，一直持有）
• 未持有股票状态，有两种未持有股票的状态
  • 状态二：已经卖出了股票，度过了冷冻期，一直没有操作，保持未持有股票状态
  • 状态三：今天卖出股票，成为未持有股票状态
• 状态四：今天为冷冻期，但冷冻期状态不可持续，只有一天

2、确定递推公式

状态一：第 i 天是持有股票状态

        成为这种状态，要么之前已经买过了，要么今天买（今天可以买，要么前一天是冷冻期，要么前一天还是未持有股票状态并且多了冷冻期）

  

• 情况一：之前已经买入了股票，dp[i][0] = dp[i - 1][0]
• 情况二：今天买
  • 前一天是冷冻期：dp[i][0] = dp[i - 1][3] - prices[i]
  • 前一天是未持有状态：dp[i][0] dp[i - 1][1] -prices[i]

        所以 dp[i][0] 在三种情况中取最大的

状态二：第 i 天是未持有股票状态，并且过了冷冻期

        成为这种状态，要么前一天就是状态二(未持有股票状态，并且过了冷冻期),要么前一天是冷冻期(状态四)，今天就成为了状态二

• 情况一：前一天已经是状态二，dp[i][1] = dp[i - 1][1]
• 情况二：前一天是冷冻期，dp[i][1] = dp[i - 1][3]

        所以dp[i][1] 在这两种情况中取最大值

状态三：第 i 天是未持有股票状态，还没过冷冻期，今天刚卖出

        成为这种状态，是今天刚卖出股票，所以前一天是持有股票状态的，只能从状态一获取到

• 情况：前一天是持有股票状态，dp[i][2] = dp[i - 1][0] + prices[i]

状态三：第 i 天是冷冻期

        成为这种状态，就是前一天刚卖出股票，只能从状态三获得到

• 情况：前一天卖股票，dp[i][3] = dp[i - 1][2]

3、初始化

        和所有买卖股票的题目一样，当天的状态都是从前一天的情况中获得的，所以应该将dp[0] 的状态全部进行初始化

• 状态一：持有股票状态，dp[0][0] = -prices[0]
• 状态二、状态三、状态四：未持有股票状态，dp[0][0] = 0

 4、遍历顺序

        从前向后进行遍历

5、获取结果

        这里与前面不同的是，要获取未持有股票状态下所有值的最大值

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

class Solution {
    public int maxProfit(int[] prices) {
 
        // 创建dp数组
        int len = prices.length;
        int[][] dp = new int[len][4];
 
        // 初始化dp数组
        dp[0][0] = -prices[0];
 
        // 推导递推公式
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i]));
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);
            dp[i][2] = dp[i-1][0] + prices[i];
            dp[i][3] = dp[i-1][2];
        }
 
        // 返回结果
        return Math.max(dp[len-1][1],Math.max(dp[len-1][2],dp[len-1][3]));
    }
}

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

题目链接：力扣

思路

        这道题和 122.买卖股票的最佳时机|| 其实是一样的，只是在卖出的时候多付一下手续费就可以，最多买卖的次数，根据天数就可以得出

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

class Solution {
    public int maxProfit(int[] prices, int fee) {
 
        // 创建的dp[]数组
        int[][] dp = new int[prices.length][2];
 
        // 初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
 
        // 推导dp数组
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i] -fee);
        }
 
        return dp[prices.length - 1][1];
    }
}