首页 > 其他分享 >线性dp:LeetCode122.买卖股票的最佳时机ll

线性dp:LeetCode122.买卖股票的最佳时机ll

时间:2024-09-10 21:14:00浏览次数:7  
标签:int ll 样例 LeetCode122 prices 无票 dp 利润

买卖股票

  • 本文所讲解的内容与LeetCode122. 买卖股票的最佳时机ll,这道题题意相同,阅读完本文后可以自行挑战一下
  • 力扣链接

题目叙述:

给定一个长度为N的数组,数组中的第i个数字表示一个给定股票在第i天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉悠前的股票)。一次买入卖出合为一笔交易。

输入格式:

第一行包含整数 N,表示天数。第二行包含N个不大于10000的正整数表示每天股票的价格。

输出格式

输出一个整数,表示最大利润。

输入样例1

6
7 1 5 3 4 6

输出样例1

7

输入样例2

5
7 6 4 3 1

输出样例2

0

样例解释:

  • 样例1:在第2天买入,在第3天卖出,这笔交易所能获得利润=5-1=4。随后在第4天买入,在第6天卖出,这笔交易所能获得利润=6-3=3。共得利润4+3 =7
  • 样例2:在这种情况下,不进行任何交易,所以最大利润为 0。

动态规划思路讲解:

  • 我们分析总利润可知,总利润是关于天数i 的函数,并且在第i天的时候,只有两种状态与之对应
    • 1.手中无票:dp[i][0]
    • 2.手中有票:dp[i][1]
  • 所以说我们可以设置dp[i][0],dp[i][1] 为状态变量,然后进行状态的转移,最终得出我们需要的答案。

1.状态变量的含义

  • dp[i][0]表示第i天,手中无票时能够获取的最大利润
  • dp[i][1]表示第i天,手中有票时能够获取的最大利润

2. 递推公式

  • 我们可以使用带权的有向图来生动的理解这个过程,我们要知道递推公式,就要了解状态转移的那个过程,也就是我们当前的状态是由以前的哪些状态推导而来。

      1. dp[i][0]表示第i天,手中无票时能获取的最大利润,我们可以通过dp[i-1][0]dp[i-1][1] ,也就是第i-1天,手中有票或者手中无票这两个状态推导而来,如果是第i-1天手中无票,那么表示没有发生交易,那么dp[i][0]=dp[i-1][0] ,反之,从i-1天有票到第i天无票,那么意味着我们在第i天卖掉了股票,此时dp[i][0]=dp[i-1][1]+w[i] ,由于我们是取最大利润,所以说是取二者的最大值,即:
      dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
      
      1. dp[i][1] 也是同理,跟上面的推导方式差不多,所以我就不在赘述了
      dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);
      
  • 所以说,总的递推公式如下:

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);

3.如何初始化?

  • 我们由这个递推公式,如何初始化边界条件呢?
  • 假设我们从第1天开始,到第n天结束,那么我们第一天的两个状态就是边界条件
dp[1][0]=0;		//第1天无票的最大利润就是0
dp[1][1]=-w[1];  //第1天就有票证明我买了第一天的那个股票

4. 遍历顺序

  • 由递推公式可知,我们的状态变量dp[i][0],dp[i][1]取决于dp[i-1][0],dp[i-1][1] 。所以说我们的遍历顺序是从前到后进行遍历。

5. 举例打印dp数组

  • 在本题,读者可以自行在for循环内进行插入printf语句进行验证我们dp数组的正确性

代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int w[N],dp[N][2];
int n;

int main(){
  scanf("%d", &n);
  for(int i=1;i<=n;i++) scanf("%d",&w[i]); 
     
  dp[1][0]=0; dp[1][1]=-w[1];
  for(int i=2; i<=n; ++i){
    dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);    
    dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);
  }
    //第n天的时候,手中无票一定是利润最大,所以说不用取二者最大值了。
  cout<<dp[n][0];
}

LeetCode122的参考代码

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		vector<vector<int> > dp(prices.size(),vector<int>(2));
        //进行初始化条件
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		for (int i = 1; i < prices.size(); i++) {
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
		}
		return dp[prices.size() - 1][0];
	}
};

标签:int,ll,样例,LeetCode122,prices,无票,dp,利润
From: https://www.cnblogs.com/Tomorrowland/p/18407226

相关文章

  • 2.2 Shell命令语言大全(小白也能看懂!)
    文章目录2.2.1Shell简介2.2.2Shell命令2.2.3Shell脚本2.2.1Shell简介Shell是一种命令行解释器,它提供了用户与操作系统内核之间的接口,允许用户通过输入命令来执行各种操作。Shell可以是命令行界面(CLI),也可以是图形用户界面(GUI)的一部分。以下是Shell的一些简......
  • RAG与LLM原理及实践(17)---Docker Redis & Python Usage
    目录背景Redis环境download修改镜像RunRedisCodingpythonredisdownload基本使用描述完整代码运行结果高阶用法序列化的方式 Snapshot与AOF快照(RDB)AOF(Append-OnlyFile)代码总结发布与订阅描述     代码运行结果注意事项解释Transanction......
  • Wordpress采集发布插件-免费下载
    推荐一款可以自动采集文章数据,并发布到Wordpress网站的Wordpress采集发布插件,支持对接简数采集器,火车头采集器,八爪鱼采集器,后羿采集器等大多数网页文章数据采集软件。Wordpress采集发布插件使用方法如下:1. 下载并安装Wordpress采集发布插件1.1 Wordpress采集发布插件免费下载......
  • Day5网络编程:epoll+服务器模型+ftp
    1.io多路复用:epollepoll的提出--》它所支持的文件描述符上限是系统可以最大打开的文件的数目;eg:1GB机器上,这个上限10万个左右。每个fd上面有callback(回调函数)函数,只有产生事件的fd才有主动调用callback,不需要轮询。注意:Epoll处理高并发,百万级1.红黑树:是特殊的二叉......
  • 【Linux】kill与kill -9
    kill命令格式kill-signalpidsignalpid是进程号,ps命令可以查看默认情况下使用kill,系统发送给进程的是SIGTERM(15)信号,告诉进程“你需要被关闭,请自行停止并退出”。kill-9fasongSIGKILL(9)信号,告诉进程“你被终结了,请立刻退出”。kill-9表示强制杀死进程,与SIGTERM......
  • DP
    动态规划动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。三个条件:最优子结构,无后效性和子问题重叠。最优子结构证明问题最优解的第一个组成部分是做出一个选择;对于一个给定问题,在其可能的第一步选择中,假定你已经知道哪种选择才会得到最优解......
  • navicat无法连接远程的mysql--Host ‘xx.xx.xx.xx‘ is not allowed to connect to th
     之前在远程虚拟机上面部署了mysql,想在本地客户端使用navicat连接数据库,结果提示:host'xxx'isnotallowedtoconnecttothismysqlserver   解决出现这个提示,是由于我们使用root用户登录时,没有给root用户设置能访问的机器,所以我们设置一下,就可以了。 1:登录mysq......
  • LLM 工程师入门:生成式 AI 的简易指南
    大模型发展了近两年,BaihaiIDP也分享了近百篇LLM各环节的技术洞察,有前沿探讨、有落地实践、有应用经验。但回头来看,我们似乎从来没有认真、从0开始探讨过LLM的基本原理。最近,一些企业客户和伙伴来询问,是否有LLM的从0到1的科普贴。他们说:"虽然在很多场景中,L......
  • [DPDK] dumpcap报错EAL init failed: is primary process running?解决办法
    [DPDK]dumpcap报错EALinitfailed:isprimaryprocessrunning?解决办法问题我写了一个DPDK程序,现在想要用DPDK自带的dpdk-dumpcap工具来抓包测试。根据官网描述,我们需要先启动我们的程序为主进程,然后启动dpdk-dumpcap为副进程。但是我直接运行dpdk-dumpcap,显示如下错误:注:......
  • Python 装饰器之__call__()
    已知我们可以用装饰器模式去实现切面功能,啊你不知,那么请看python装饰器模式实现切面功能。除此之外还有其他方式去实现切面功能吗?当然有,那就是python的__call__()方法,call()是一个特殊方法,用于将一个类实例变成一个可调用的对象,即可以像函数一样调用这个类。当调用一个类实例时......