代码随想录算法训练营day50

ops/2024/9/24 14:23:44/

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

五部曲:

dp数组下标及含义:

  • dp[i][0] 表示未操作;
  • dp[i][1]表示第一次持有;
  • dp[i][2]表示第一次未持有;
  • dp[i][3]表示第二次持有;
  • dp[i][4]表示第二次未持有

dp数组初始化:

  • dp[i][0]=0;
  • dp[i][1]=-prices[0];
  • dp[i][2]=0;
  • dp[i][3]=-prices[0];
  • dp[i][4]=0

递推公式:

  • dp[i][0]=dp[i-1][0];
  • dp[i][1] = max(dp[i - 1][1], dp[i][0]-prices[i]);
  • dp[i][2] = max(dp[i - 1][2], prices[i] + dp[i - 1][1]);
  • dp[i][3] = max(dp[i-1][3],dp[i][2]-prices[i]);
  • dp[i][4] = max(dp[i-1][4],dp[i][3]+prices[i])

遍历方向:从前到后遍历

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for(int i=1;i<prices.size();i++){dp[i][0] = dp[i - 1][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[prices.size()-1][4];}
};

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

思路: 本题和上一题区别在于可以买卖k次,因此奇数是买入,偶数是卖出
五部曲:

dp数组下标及含义:

  • dp[i][0] 表示未操作;
  • dp[i][1]表示第一次持有;
  • dp[i][2]表示第一次未持有;
  • dp[i][3]表示第二次持有;
  • dp[i][4]表示第二次未持有

dp数组初始化:

  • dp[i][0]=0;
  • dp[i][1]=-prices[0];
  • dp[i][2]=0;
  • dp[i][3]=-prices[0];
  • dp[i][4]=0

当为奇数时都初始化为-prices[0]

递推公式:

  • dp[i][0]=dp[i-1][0];
  • dp[i][1] = max(dp[i - 1][1], dp[i][0]-prices[i]);
  • dp[i][2] = max(dp[i - 1][2], prices[i] + dp[i - 1][1]);
  • dp[i][3] = max(dp[i-1][3],dp[i][2]-prices[i]);
  • dp[i][4] = max(dp[i-1][4],dp[i][3]+prices[i])

遍历方向:从前到后遍历

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.size() == 0)return 0;vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1; i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

http://www.ppmy.cn/ops/14854.html

相关文章

react入门基础

React 简介 React ------- 用于构建用户界面的JavaScript库/一个将数据渲染为HTML视图的开源JavaScript库 React历史 【经典水时长/水字数】 由Facebook开发&#xff0c;且开源 起初由Facebook的软件工程师 Jordan Walke 创建 【膜拜 React 祖师爷】于2011年部署于 Facebo…

Webfunny大版本改造(mysql迁移至clickhouse)

前段时间webfunny整个技术团队&#xff0c;都在忙着改造webfunny的clickhouse版。改造的内容非常之多&#xff0c;工作量非常之大&#xff0c;以至于有些技术小伙伴提的优化建议、在那段时间暂时被搁置&#xff0c;除非是比较严重的bug。 好在经过几个月的加班加点改造到上线&…

计算机网络原原理学习资料分享---第一章/第一节(为有梦想的自己加油!)

计算机网络原理 课程知识框架 计算机网络原理 课程框架 第一章 计算机网络概述 重点 第二章 网络应用 重点 第三章 传输层 重点 难点 第四章 网络层…

linux进阶篇:ftp的概念特点及安装配置过程

Linux搭建ftp服务&#xff1a;ftp的应用案例及其概念特点 一、ftp介绍 &#xff08;File Transfer Protocol&#xff0c;文件传输协议&#xff09;是一种在互联网中进行文件传输的协议&#xff0c;基于客户端/服务器模式。它使用TCP/IP协议进行通信&#xff0c;默认使用20和2…

如何在setup()函数之外的其他地方需要访问路由器(router)

如果在setup()函数之外的其他地方需要访问路由器(router)&#xff0c;可以使用getCurrentInstance()函数获取当前组件实例&#xff0c;然后从中访问路由器。下面是一个示例&#xff1a; import { getCurrentInstance } from vue;// 在需要访问路由器的地方 const instance ge…

SpringBootWeb 请求与响应 --学习笔记

在浏览器发起请求时&#xff0c;后端的web服务器是如何响应的&#xff1f; 通过自定义的Controller控制器类——请求会被部署在Tomcat中的Controller接收&#xff0c;然后Controller再给浏览器一个响应&#xff0c;在请求响应的过程中是遵循HTTP协议的 但其实Tomcat是不识别我…

PostgreSQL的扩展(extensions)-常用的扩展之pg_stat_statements

PostgreSQL的扩展&#xff08;extensions&#xff09;-常用的扩展之pg_stat_statements 基础信息 OS版本&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本&#xff1a;16.2 pg软件目录&#xff1a;/home/pg16/soft pg数据目录&#xff1a;/home/pg16/…

解决Django中调页面时出现“Did you forget to register or load this tag”报错

解决Django中调页面时出现“Did you forget to register or load this tag?”报错 1.问题收录 2.分析问题 在HTML文件中&#xff0c;{{title}}&#xff0c;{{lanyy}}&#xff0c;django 默认规定的语法&#xff0c;用{{}}包起来的变量叫做模板变量。 django渲染模板时会将大…