代码随想录算法训练营第四十九天 | LeetCode 123. 买卖股票的最佳时机 III、188. 买卖股票的最佳时机 IV

简介: 代码随想录算法训练营第四十九天 | LeetCode 123. 买卖股票的最佳时机 III、188. 买卖股票的最佳时机 IV

代码随想录算法训练营第四十九天 | LeetCode 123. 买卖股票的最佳时机 III、188. 买卖股票的最佳时机 IV

文章链接:123. 买卖股票的最佳时机 III188. 买卖股票的最佳时机 IV

视频链接:123. 买卖股票的最佳时机 III188. 买卖股票的最佳时机 IV

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

1.1 思路

  1. 121. 买卖股票的最佳时机是在数组中只能买卖一次,122. 买卖股票的最佳时机 II是在数组中可以买卖多次,本题是在数组中至多买卖 2 次,可以 0 次、1 次、2 次
  2. dp 数组及其下标的含义:第 i 天 dp[i][0] 表示不操作,dp[i][1] 表示第 1 次持有,不一定是在第 i 天才买入的,因此是持有,dp[i][2] 表示第 1 次不持有,dp[1][3] 表示第 2 次持有,dp[i][4] 表示第 2 次不持有。以上就是本题的 5 种状态都表示出来了
  3. 递推公式:dp[i][0]=dp[i-1][0],由前一天延续下来;dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])即延续前一天持有的状态,或者由前一天不操作然后买入变为第 1 次持有,取最大值是因为求的是手头上最多的现金;dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i])即延续前一天不持有的状态,或者由前一天第 1 次持有然后卖出变为第 1 次不持有;dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i])即延续前一天持有的状态,或者由前一天第 1 次不持有然后买入变为第 2 次持有的;dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i])即延续前一天不持有的状态,或者由前一天第 2 次持有然后卖出变为第 2 次不持有的
  4. dp 数组的初始化:从递推公式可以看出都是由前一个状态推导出来的,因此 dp[0][0]=0 因为没操作, dp[0][1]=0-prices[0] 因为第 1 次持有, dp[0][2]=0 因为第 1 次不持有,可以理解为第 0 天买入又在第 0 天卖出了,这是可以的, dp[0][3]=0-prices[i] 因为第 2 次持有,第 1 次的持有与不持有都在同一天买入和卖出了,dp[0][4]=0 因为第 2 次不持有,同理是第 0 天买入和卖出了
  5. 遍历顺序:从递推公式可以看出从前往后 for(int i=1;i<length;i++)从 1 开始是因为第 0 天已经初始化了。最终因为不持有的状态就是卖出了的状态肯定比持有还没卖出的状态有钱,因此是返回 dp[i][2] 和 dp[i][4] 之间取最大值。其实直接返回 dp[length-1][4] 也可以,这里就包括了 dp[length-1][2] 了。你可能疑惑我在第 1 次卖出的时候就是最大值了,其实没关系,如果这个是最大值了,那我再当天买入再卖出也同样是最大值,这就是 dp[length-1][4] 包括了 dp[length-1][2]
  6. 打印 dp 数组:用于 debug

1.2 代码

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;
        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[len - 1][4];
    }
}

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

2.1 思路

  1. 123. 买卖股票的最佳时机 III中我们至多只能买卖两次,本题是至多买卖 k 次。其实两题联系是很紧密的。
  2. dp 数组及其下标的含义:在123. 买卖股票的最佳时机 III中至多买卖 2 次就已经列到了 dp[i][4] 了,因为买卖一次就要有一次买入一次卖出。因此至多买卖 k 次的话每多一次就要多 2 个空位表示状态,因此 dp 数组应该定义成 dp[prices.length][2k+1] 第一维度就是数组大小,第二维度就是 2k+1 这么大,因为下标到 2k+1 这么大。dp 数组的含义和123. 买卖股票的最佳时机 III是一样的,可以看出规律第二维度的数字如果是奇数就是持有,偶数就是不持有。比如 dp[i][1] 就是持有,dp[i][2] 就是不持有
  3. 递推公式:我们需要一个 for循环才能把这些状态都表示出来。第二维度的下标都用 j 表示 for(int i=0;i<prices.length;i++)for(int j=0;j<2k;j+=2)持有状态:dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i])这里即从前一天持有的状态延续,或者由前一天不持有的状态买入变为持有;不持有状态:dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])这里即从前一天不持有的状态延续,或者由前一天持有的状态卖出变为不持有。j 这层 for循环后面 j<2k 是因为我们在下面进行了加一,比如 k 等于 2,那 dp[i][1] 和 dp[i][2] 都是 k=1 时的状态,dp[i][3] 和 dp[i][4] 都是 k=2 时的状态
  4. dp 数组的初始化:根据递推公式初始化第 0 天的状态,第二维度的下标的状态是在只有奇数的情况才会 0-prices[i],都表示为第几次持有,就通过 for(int j=1;j<2k;j+=2)dp[0][j]=0-prices[i],这里 j 从 1 开始是因为 dp[0][1] 是第 1 次买入持有,从这里开始,为什么 j<2k,同样代入个数字,k=2 时,j=3<2*2 同样可以把 dp[0][3] 这个奇数的情况初始化
  5. 遍历顺序:从前往后遍历
  6. 打印 dp 数组:用于 debug

2.2 代码

// 版本二: 二维 dp数组
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;
        // [天数][股票状态]
        // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
        int len = prices.length;
        int[][] dp = new int[len][k*2 + 1];
        // dp数组的初始化, 与版本一同理
        for (int i = 1; i < k*2; i += 2) {
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k*2 - 1; j += 2) {
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[len - 1][k*2];
    }
}


相关文章
|
4月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
58 0
|
3月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
45 2
|
6月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
67 1
|
6月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
89 1
|
27天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
27天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
134 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
1月前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
1月前
|
算法
基于龙格库塔算法的锅炉单相受热管建模与matlab数值仿真
本设计基于龙格库塔算法对锅炉单相受热管进行建模与MATLAB数值仿真,简化为喷水减温器和末级过热器组合,考虑均匀传热及静态烟气处理。使用MATLAB2022A版本运行,展示自编与内置四阶龙格库塔法的精度对比及误差分析。模型涉及热传递和流体动力学原理,适用于优化锅炉效率。