动态规划Day12(股票问题终结,有点疑惑)

目录

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

看到题目的第一想法? ? ? ? ? ? ? ?

看到代码随想录之后的想法

自己实现过程中遇到的困难

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

看到题目的第一想法? ? ? ? ? ? ? ?

看到代码随想录之后的想法

自己实现过程中遇到的困难

---

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

力扣题目链接(opens new window)

给定一个整数数组，其中第?i?个元素代表了第?i?天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

• 输入: [1,2,3,0,2]
• 输出: 3
• 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

看到题目的第一想法
? ? ? ? ? ? ? ?

? ? ? ? 回忆一下之前的股票问题是怎么做的？

? ? ? ? dp[i][0] 买入股票的最大现金

? ? ? ? ? ? ? ? ? ? ? ? 则为? 之前买入的，当天买入的(用前一天的冷冻期来-)

? ? ? ? ? ? ? ? ? ? ? ? Math.max(dp[i-1][0],dp[i-1][3]-prices[i]);

? ? ? ? dp[i][1] 卖出股票的最大现金

? ? ? ? ? ? ? ? ? ? ? ? Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);

? ? ? ? 我考虑加上一个 dp[i][3] 当天若为冷冻期的现金?

? ? ? ? ? ? ? ? ? ? ? ? 则直接为dp[i-1][1],不管是不是冷冻期都默认为dp[i-1][1]

????????

看到代码随想录之后的想法

? ? ? ? ? ? ?代码随想录分析思路更加详细

? ? ? ? ?dp[i][j]:j有四种情况

? ? ? ? ?一.?dp[i][0] 买入股票的最大现金

? ? ? ? ? ? ? ? 1之前买入 dp[i-1][0]

? ? ? ? ? ? ? ? 2当天买入

? ? ? ? ? ? ? ? ? ? ? ? 1 当天之前是冷冻期

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i-1][3]-price[i]??

? ? ? ? ? ? ? ? ? ? ? 2 当天之前不是冷冻期

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?dp[i-1][1]-price[i]

? ? ? ? ? ? ?二.?dp[i][1] 之前卖出的最大现金

? ? ? ? ? ? ? ? 1 当天之前是冷冻期

? ? ? ? ? ? ? ? ? ? ? ? dp[i-1][3]

? ? ? ? ? ? ? ? 2 当天之前不是冷冻期

? ? ? ? ? ? ? ? ? ? ? ? dp[i-1][1]

? ? ? ? ? ? ? 三.dp[i][2] 当天卖出的最大现金

? ? ? ? ? ? ? ? ? ? ? ?dp[i-1][0]+prices[i]

? ? ? ? ? ? ? 四.?dp[i][3] 冷冻期的最大现金代码

? ? ? ? ? ? ? ? ? ? ? ? 则为前一天卖出的最大现金 dp[i-1][2]

? ? ? ??

? ? ? ? 打印dp数组时，应该为 Math.max(dp[i][2],dp[i][3],dp[i][4])

自己实现过程中遇到的困难

? ? ? ? 卡哥的做法：需要理清卡哥给的关系

? ? ? ? 打印dp的值需要注意

class Solution {
    public int maxProfit(int[] prices) {
        /*
        //买入，卖出，冷冻期，买入，卖出，冷冻期
        //题意是要算出最大利润，但是需要尽可能地完成多的交易？
        //定义dp数组和每个下标的含义
        //冷冻期的最大金额？
        // dp[i][j] dp[i][0] 买入的最大金额，
        // dp[i][1]卖出的最大金额,
        // dp[i][2]冷冻期的最大金额
        //定义递推公式
        //冷冻期的最大金额-price[i]
        //dp[i][0] 买入时的最大值Math。max(dp[i-1][0],dp[i-1][2]-price[i]);
        //dp[i][1] 卖出时的最大值Math。max(dp[i-1][1],dp[i-1][0]+price[i]);
        //dp[i][2] 冷冻期 dp[i-1][1]
        //dp数组初始化
        //确定遍历顺序
        //从左至右
        //举例推导dp数组
        int[][] dp = new int[prices.length][3];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        for(int i=1;i<prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
            dp[i][2] = dp[i-1][1];
        }
        return dp[prices.length-1][1];*/
        //我的做法不够细致，有些地方模棱两可，没有卡哥思路写的那么清晰
        //卡哥思路：
        //一天存在的状态
        //1 买入股票
        //  1 当天买入，前一天为冷冻期 dp[i-1][3]+prices[i]
        //  2 当天买入，前一天不为冷冻期 dp[i-1][1]+prices[i]
        //  3 之前就买入 dp[i-1][0]
        //2 之前卖出股票
        //  1 若当天之前为冷冻期
        //  dp[i-1][3]
        //  2 若当天之前不为冷冻期
        //  dp[i-1][1]
        //3 当天卖出股票
        //  dp[i-1][0]+prices[i]
        //4 当天为冷冻期
        //  dp[i-1][2]
        //初始化
        //dp[0][0] = -price[i] 其他都为0,看dp的递推公式，应该都赋值为0
        //遍历顺序，从前往后
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        for(int i=1;i<prices.length;i++){
            //前一天为冷冻期，前一天不为冷冻期
            dp[i][0] = Math.max(Math.max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]),dp[i-1][0]);
            //之前卖出，要考虑前一天是冷冻期or不是冷冻期
            dp[i][1] = Math.max(dp[i-1][3],dp[i-1][1]);
            //当天卖出
            dp[i][2] = dp[i-1][0]+prices[i];
            //当天为冷冻期，则前一天卖出
            dp[i][3] = dp[i-1][2];
        }
        
        //return 应该是123 之前写成了012 报错
        return Math.max(dp[prices.length-1][3],Math.max(dp[prices.length-1][1],dp[prices.length-1][2]));
    }
}

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

力扣题目链接(opens new window)

给定一个整数数组?prices，其中第?i?个元素代表了第?i?天的股票价格 ；非负整数?fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:

• 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
• 输出: 8

解释: 能够达到的最大利润:

• 在此处买入?prices[0] = 1
• 在此处卖出 prices[3] = 8
• 在此处买入 prices[4] = 4
• 在此处卖出 prices[5] = 9
• 总利润:?((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意:

• 0 < prices.length <= 50000.
• 0 < prices[i] < 50000.
• 0 <= fee < 50000.

看到题目的第一想法
? ? ? ? ? ? ? ?

? ? ? ? 回忆一下之前的股票问题是怎么做的？

? ? ? ? dp[i][0] 买入股票的最大现金 减去相关的手续费即可

? ? ? ? ? ? ? ? ? ? ? ? Math.max(dp[i-1][0],dp[i-1][3]-prices[i]-fee);

? ? ? ? dp[i][1] 卖出股票的最大现金

? ? ? ? ? ? ? ? ? ? ? ? Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);

? ? ? ? ?1 应该怎么初始化？

? ? ? ? 我的初始化是

????????dp[0][0] = -prices[0]-fee

? ? ? ? dp[0][1] = dp[0][0]+prices[0](是有问题的)

? ? ? ??

看到代码随想录之后的想法

? ? ? ? 代码随想录分析思路更加详细

? ? ? ? ?dp[i][j]:情况分析

????????

? ? ? ? dp[i][0] 买入股票的最大现金

? ? ? ? ? ? ? ? ? ? ? ? Math.max(dp[i-1][0],dp[i-1][3]-prices[i]);

? ? ? ? dp[i][1] 卖出股票的最大现金 加上相关的手续付费

? ? ? ? ? ? ? ? ? ? ? ? Math.max(dp[i-1][1],dp[i-1][0]+prices[i]+fee);

? ? ? ? 只需要初始化dp[0][0]=-prices[0]

? ? ? ? 打印dp数组时，为什么是Math.max(dp[prices.length][0],dp[prices.length[1]]);

自己实现过程中遇到的困难

? ? ? ? ? ? ? ?不理解

????????????????初始化：dp[0][1]为何不用初始化

????????????????打印 ：为何打印两个值？

????????

class Solution {
    public int maxProfit(int[] prices, int fee) {
        //需要算进去一个手续费用
        //买的时候需要加上手续费
        //确定dp数组以及每个下标的含义
        //dp[i][0] 买入股票的最大值 Math.max(dp[i-1][1]-prices[i]-2,dp[i-1][0]);
        //dp[i][1] 卖出股票的最大值 Math.max(dp[i-1][1],dp[i-1][0]+price[i]);
        //确定递推公式
        //dp数组初始化
        //dp[i][0]=-price[0];
        //确定遍历顺序
        //从前往后
        
        int[][] dp = new int[prices.length][2];
        dp[0][0]=-prices[0]-fee;
        dp[0][1]=0;
        for(int i=1;i<prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][1]-prices[i]-fee,dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return Math.max(dp[prices.length-1][1],dp[prices.length-1][0]);
        
        /*
        int[][] dp = new int[prices.length][2];
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
            //卡哥做法，卖出股票才付手续费 手续费为fee 之前写成了2
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
        }
        return Math.max(dp[prices.length-1][1],dp[prices.length-1][0]);*/
    }
}