当前位置: 首页 > news >正文

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

动态规划

  • 思路:
    • 状态定义
      • 假设 buy[i][j] 是第 i 天进行第 j 笔交易,手上还买入一支股票的最大利润;
      • sell[i][j] 是第 i 天进行第 j 笔交易的最大利润;
    • 状态转移:
      • 第 i 天进行第 j 笔交易,手上还买入一支股票:
        • 第 i - 1 天即为此状态,第 i 天未进行操作,即 buy[i - 1][j];
        • 第 i - 1 天进行第 j 笔交易,第 i 天买入,即 sell[i - 1][j] - prices[i];
        • 则 buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
      • 第 i 天进行第 j 笔交易:
        • 第 i - 1 天进行了第 j 笔交易,第 i 天未进行操作,即 sell[i - 1][j];
        • 第 i - 1 天进行了第 j - 1 笔交易并且手上还持有一支股票,第 i 天进行卖出,即 buy[i - 1][j - 1] + prices[i];
        • 则 sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
    • 初始状态:
      • buy[0][0] = -prices[0]
      • sell[0][0] = 0
      • 初始化第 0 天第 0 - k 笔交易值为 INT_MIN / 2;

        buy[0][i] = INT_MIN / 2;

        sell[0][i] = INT_MIN / 2;

    • 最大交易次数为天数的一半,即 k = std::min(k, size / 2);
    • 第 0 笔交易的时候进行修正(避免 j - 1 溢出)

      buy[i][0] = std::max(buy[i - 1][0], sell[i - 1][0] - prices[i]);

    • 最大利润为最后一天完成交易的最大值:

      *std::max_element(sell[size - 1].begin(), sell[size - 1].end());

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int size = prices.size();if (0 == size) {return 0;}k = std::min(k, size / 2);std::vector<std::vector<int>> buy(size, std::vector<int>(k + 1));std::vector<std::vector<int>> sell(size, std::vector<int>(k + 1));buy[0][0] = -prices[0];sell[0][0] = 0;for (int i = 1; i <= k; ++i) {buy[0][i] = INT_MIN / 2;sell[0][i] = INT_MIN / 2;}for (int i = 1; i < size; ++i) {buy[i][0] = std::max(buy[i - 1][0], sell[i - 1][0] - prices[i]);for (int j = 1; j <= k; ++j) {buy[i][j] = std::max(buy[i - 1][j], sell[i - 1][j] - prices[i]);sell[i][j] = std::max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);}}return *std::max_element(sell[size - 1].begin(), sell[size - 1].end());}
};

相关文章:

  • cissp 第10章 : 物理安全要求
  • PHP中excel带图片数据导入
  • Centos 磁盘挂载和磁盘扩容(新加硬盘方式)
  • <HarmonyOS第一课>1~10课后习题汇总
  • 使用HttpSession和过滤器实现一个简单的用户登录认证的功能
  • ControlNet构图控制
  • PCL 格网法计算点云的占地面积
  • React16源码: React中创建更新的方式及ReactDOM.render的源码实现
  • 收到的字符串写入xml并且将这个xml写入.zip文件中
  • 【设计模式】工厂模式
  • 【动态规划】C++算法:446等差数列划分 II - 子序列
  • 带前后端H5即时通讯聊天系统源码
  • ES-极客学习第二部分ES 入门
  • 二叉树的层序遍历经典问题(算法村第六关白银挑战)
  • 缓存cache和缓冲buffer的区别
  • 【108天】Java——《Head First Java》笔记(第1-4章)
  • 【前端学习】-粗谈选择器
  • CSS魔法堂:Absolute Positioning就这个样
  • Javascript设计模式学习之Observer(观察者)模式
  • Mocha测试初探
  • React Transition Group -- Transition 组件
  • weex踩坑之旅第一弹 ~ 搭建具有入口文件的weex脚手架
  • 安装python包到指定虚拟环境
  • 给github项目添加CI badge
  • 可能是历史上最全的CC0版权可以免费商用的图片网站
  • 面试题:给你个id,去拿到name,多叉树遍历
  • 王永庆:技术创新改变教育未来
  • 为视图添加丝滑的水波纹
  • 新版博客前端前瞻
  • 教程:使用iPhone相机和openCV来完成3D重建(第一部分) ...
  • ​ 无限可能性的探索:Amazon Lightsail轻量应用服务器引领数字化时代创新发展
  • ​​​​​​​ubuntu16.04 fastreid训练过程
  • ​二进制运算符:(与运算)、|(或运算)、~(取反运算)、^(异或运算)、位移运算符​
  • ###STL(标准模板库)
  • (¥1011)-(一千零一拾一元整)输出
  • (2)(2.4) TerraRanger Tower/Tower EVO(360度)
  • (附源码)springboot车辆管理系统 毕业设计 031034
  • (黑马C++)L06 重载与继承
  • (机器学习-深度学习快速入门)第一章第一节:Python环境和数据分析
  • (论文阅读11/100)Fast R-CNN
  • (数据结构)顺序表的定义
  • (算法二)滑动窗口
  • (续)使用Django搭建一个完整的项目(Centos7+Nginx)
  • (转)Linq学习笔记
  • (转)清华学霸演讲稿:永远不要说你已经尽力了
  • (轉)JSON.stringify 语法实例讲解
  • **CI中自动类加载的用法总结
  • ./indexer: error while loading shared libraries: libmysqlclient.so.18: cannot open shared object fil
  • .NET Standard / dotnet-core / net472 —— .NET 究竟应该如何大小写?
  • .NET 发展历程
  • .NET 中的轻量级线程安全
  • .NET/MSBuild 中的发布路径在哪里呢?如何在扩展编译的时候修改发布路径中的文件呢?
  • .NET关于 跳过SSL中遇到的问题
  • .NET学习教程二——.net基础定义+VS常用设置
  • @RequestBody与@ModelAttribute