Day43 | 动态规划 ：状态机DP 买卖股票的最佳时机买卖股票的最佳时机II

devtools/2024/11/19 0:44:47/

Day43 | 动态规划 ：状态机DP 买卖股票的最佳时机&&买卖股票的最佳时机II

动态规划应该如何学习？-CSDN博客

本次题解参考自灵神的做法，大家也多多支持灵神的题解

买卖股票的最佳时机【基础算法精讲 21】_哔哩哔哩_bilibili

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

文章目录

  • Day43 | 动态规划 ：状态机DP 买卖股票的最佳时机&&买卖股票的最佳时机II
    • 121.买卖股票的最佳时机
      • 思路分析（子问题）：
        • 重点：
          • 如果我第i天持有股票，status==1，dfs（i，1）
          • 如果我第i天没有股票，status==0，dfs（i，0）
      • 1.回溯 DFS
      • 2.记忆化搜索
      • 3.1:1翻译为动态规划
    • 122.买卖股票的最佳时机II

121.买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

思路分析（子问题）：

最后一天发生了什么？

输入：[7,1,5,3,6,4]
输出：5

从低0天开始到第五天结束时的利润=从第0天开始到第四天结束时的利润+第五天的利润

第五天的利润有三种可能（就光说第五天这一天）

1.我啥也没干那就是0，因为我没有买进也没有卖出

2.我把我有的股票给卖了，那就是4，即prices[5]

3.我本来就没股票，我今天买入了，那就是-4，即-prices[5]

为什么是负的利润还要买？因为你卖的前提是你买了。

然后就是熟悉的往前推，从0到第四天结束的利润是前三天的利润+第四天的直到第0天

可以发现我们需要一个bool值来体现我们现在是否持有股票，false表示没有，true表示有

大家要注意理解：

我第i-1天的结束就是第i天的开始

重点：

dfs(i,status)的含义就是我从第0天到第i天，在status状态下所能得到的最大金额，status就是咱们提到的bool值0或1

如果我第i天持有股票，status==1，dfs（i，1）

那我第一个可能是我第i-1天就有股票但是我没卖掉，即i-1天的时候也有股票，那我在从0-i这几天的最大金额就肯定是dfs(i-1,1)

也有可能是我在第i天的时候买了，那说明我前面都没买也没卖，那前i-1天的总利润就是0，第i天的利润就是-prices[i]

dfs(i,1)=max(dfs(i-1,1),-prices[i])
如果我第i天没有股票，status==0，dfs（i，0）

那我第一个可能是我第i-1天就没有股票，然后今天也没买，那我在从0到i这几天的最大金额就肯定是dfs(i-1,0)

也有可能是我在0到i天中间买了股票了，一直没卖，到了今天才卖掉了，那我第i天的利润就是dfs(i-1,1)+prices[i]，因为你得保证你卖出的时候你的前一天是有股票的，不然卖啥啊对吧

（买的时候花的钱已经算到买的那天的利润里面去了，是负的）

dfs(i,0)=max(dfs(i-1,0),dfs(i-1,1)+prices[i])

最后返回的是什么，那肯定是最后一天不持有股票的情况，就是我们要的最大值了

image-20241113163933787

这样的表示状态转移的图叫做状态机，从图中可以明显的看出状态的转移

大家把买入部分的dfs(i-1,0)当做0，就是本题的状态转移，正如上面所说，dfs(i-1,0)说的是我前一天没有股票的最大利润，这题里面我只要i-1天没有股票，那说明我前面都没买过股票，利润只能是0

image-20241113164118781

结合灵神的图更好理解

image-20241113164358703

1.回溯 DFS

1.返回值和参数

i是每天的价格

status是状态，表示是否持有股票

int dfs(int i,int status,vector<int>& prices)

2.终止条件

dfs(-1,0)表示前-1天不持有股票的利润，那自然是零

dfs(-1,1)表示前-1天持有股票的利润，这显然是不合法的状态，因为前-1天的时候还不能买股票，更不能卖，所以返回负无穷

		if(i<0)if(status==true)   return INT_MIN;else    return 0;

3.本层逻辑

如递推公式所说，我有股票，那就从有股票的两种情况选个最大的

没有股票就从没有股票的两种情况选个最大的

		if(status==1)return max(dfs(i-1,1,prices),-prices[i]);else    return max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);

完整代码：

当然，这是超时的

class Solution {
public:int dfs(int i,int status,vector<int>& prices){if(i<0)if(status==true)   return INT_MIN;else    return 0;if(status==1)return max(dfs(i-1,1,prices),-prices[i]);else    return max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);}int maxProfit(vector<int>& prices) {return dfs(prices.size()-1,0,prices);}
};

2.记忆化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

class Solution {
public:int dfs(int i,int status,vector<int>& prices,vector<vector<int>>& dp){if(i<0)if(status==true)   return INT_MIN;else    return 0;if(dp[i][status]!=-1)return dp[i][status];if(status==1)return dp[i][status]=max(dfs(i-1,1,prices,dp),-prices[i]);else    return dp[i][status]=max(dfs(i-1,0,prices,dp),dfs(i-1,1,prices,dp)+prices[i]);}int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,-1));return dfs(prices.size()-1,0,prices,dp);}
};

3.1:1翻译为动态规划

1.确定dp数组以及下标的含义

dp数组是前i天可以取得的最大利润

下标笔者采用dp的i对应prices的i-1，防止dp数组下标出现负数（影响的知识dp数组中的位置，对结果不影响的）

也会给出dp数组和prices下标对应的，即dp数组下标就是天数

2.确定递推公式

//第i天没股票
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
//第i天有股票
dp[i][1]=max(dp[i-1][1],-prices[i]);

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

3.dp数组如何初始化

DP数组下标从0开始

第0天没有股票，利润为0，dp[0][0]=0;

第0天有股票，那肯定买的第0天的，利润为-prices[i]，dp[0][1]=-prices[i];

DP数组下标从1开始

dfs中的第-1天对应dp的第0天

//dfs(-1,0)对应dp[0][0]
//dfs(-1,1)对应dp[0][1]
dp[0][0]=0;
dp[0][1]=INT_MIN;

和回溯中终止条件对应

4.确定遍历顺序

后续结果需要依赖前面的计算结果，故使用从前往后遍历

		for(int i=0;i<prices.size();i++){dp[i+1][0]=max(dp[i][0],dp[i][1]+prices[i]);dp[i+1][1]=max(dp[i][1],-prices[i]);}

完整代码

//避免出现负数下标的情况 dp下标从1开始
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size()+1,vector<int>(2,0));dp[0][0]=0;dp[0][1]=INT_MIN;for(int i=0;i<prices.size();i++){dp[i+1][0]=max(dp[i][0],dp[i][1]+prices[i]);dp[i+1][1]=max(dp[i][1],-prices[i]);}   return dp[prices.size()][0];}
};

//dp下标从0开始
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

122.买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

image-20241113163933787

这样的表示状态转移的图叫做状态机，从图中可以明显的看出状态的转移

image-20241113164118781

结合灵神的图更好理解

image-20241113164358703

和上一题的区别就是，这里的股票可以买卖多次

体现在如果我第i天有股票的话，我可能前面买过股票

 dfs(i,1)=max(dfs(i-1,1,prices),dfs(i-1,0,prices)-prices[i]);

而上一题是

dfs(i,1)=max(dfs(i-1,1),-prices[i])

直接写-prices[i]（其实是0-prices[i]）是因为如果你在第i天买进，前面肯定没买过，因为上一题只能买一次，0到i-1天的最大利润只可能是0

本题是前面可能买卖过，可能0到i-1天的最大利润不为0

1.回溯法

class Solution {
public:int dfs(int i,int status,vector<int>& prices){if(i<0)if(status==1)return INT_MIN;elsereturn 0;if(status==1)return max(dfs(i-1,1,prices),dfs(i-1,0,prices)-prices[i]);elsereturn max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);}int maxProfit(vector<int>& prices) {return dfs(prices.size()-1,0,prices);}
};

//lambda
class Solution {
public:int maxProfit(vector<int>& prices) {function<int(int,int)> dfs=[&](int i,int status)->int{if(i<0)if(status==1)return INT_MIN;elsereturn 0;if(status==1)return max(dfs(i-1,1),dfs(i-1,0)-prices[i]);elsereturn max(dfs(i-1,0),dfs(i-1,1)+prices[i]);};return dfs(prices.size()-1,0);}
};

2.记忆化搜索

class Solution {
public:int dfs(int i,int status,vector<int>& prices,vector<vector<int>>& dp){if(i<0)if(status==1)return INT_MIN;elsereturn 0;if(dp[i][status]!=-1)return dp[i][status];if(status==1)return dp[i][status]=max(dfs(i-1,1,prices,dp),dfs(i-1,0,prices,dp)-prices[i]);elsereturn dp[i][status]=max(dfs(i-1,0,prices,dp),dfs(i-1,1,prices,dp)+prices[i]);}int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,-1));return dfs(prices.size()-1,0,prices,dp);}
};

//lambda
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,-1));function<int(int,int)> dfs=[&](int i,int status)->int{if(i<0)if(status==1)return INT_MIN;elsereturn 0;if(dp[i][status]!=-1)return dp[i][status];if(status==1)return dp[i][status]=max(dfs(i-1,1),dfs(i-1,0)-prices[i]);elsereturn dp[i][status]=max(dfs(i-1,0),dfs(i-1,1)+prices[i]);};return dfs(prices.size()-1,0);}
};

3.动态规划

这里的dp数组下标是从0开始的

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

和记忆化搜索对应的

dp数组下标从1开始，避免了负数下标的状态

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

http://www.ppmy.cn/devtools/135074.html

相关文章

JAVA开源项目 微服务在线教育系统 计算机毕业设计

JAVA开源项目 微服务在线教育系统 计算机毕业设计

博主说明&#xff1a;本文项目编号 T 060 &#xff0c;文末自助获取源码 \color{red}{T060&#xff0c;文末自助获取源码} T060&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…
阅读更多...
搭建Spring gateway网关微服务

搭建Spring gateway网关微服务

在使用微服务架构时&#xff0c;往往我们需要搭建一个网关服务&#xff0c;作为各个微服务的统一入口。Spring gateway作为网关服务的后起之秀&#xff0c;受到各大企业的欢迎。下面介绍下网关服务Spring gateway的搭建。 引入依赖&#xff0c;这一步比较重要&#xff0c;也需要…
阅读更多...
前端无感刷新token

前端无感刷新token

摘要&#xff1a; Axios 无感知刷新令牌是一种在前端应用中实现自动刷新访问令牌&#xff08;access token&#xff09;的技术&#xff0c;确保用户在进行 API 请求时不会因为令牌过期而中断操作 目录概览 XMLHttpRequestAxiosFetch APIJQuni.request注意事项&#xff1a; 访问…
阅读更多...
Nature Communications 基于触觉手套的深度学习驱动视触觉动态重建方案

Nature Communications 基于触觉手套的深度学习驱动视触觉动态重建方案

在人形机器人操作领域&#xff0c;有一个极具价值的问题&#xff1a;鉴于操作数据在人形操作技能学习中的重要性&#xff0c;如何有效地从现实世界中获取操作数据的完整状态&#xff1f;如果可以&#xff0c;那考虑到人类庞大规模的人口和进行复杂操作的简单直观性与可扩展性&a…
阅读更多...
Python爬虫----python爬虫基础

Python爬虫----python爬虫基础

一、python爬虫基础-爬虫简介 1、现实生活中实际爬虫有哪些&#xff1f; 2、什么是网络爬虫&#xff1f; 3、什么是通用爬虫和聚焦爬虫&#xff1f; 4、为什么要用python写爬虫程序 5、环境和工具 二、python爬虫基础-http协议和chrome抓包工具 1、什么是http和https协议…
阅读更多...
简单的爬虫脚本编写

简单的爬虫脚本编写

一、数据来源分析 想爬取一个网站的数据&#xff0c;我们首先要进行数据分析。通过浏览器F12开发者工具栏进行抓包&#xff0c;可以分析我们想要的数据来源。 通过关键字搜索&#xff0c;可以找到相对应的数据包 二、爬虫实现 需要用到的模块为&#xff1a;request&#xf…
阅读更多...
基于BERT的情感分析

基于BERT的情感分析

基于BERT的情感分析 1. 项目背景 情感分析&#xff08;Sentiment Analysis&#xff09;是自然语言处理的重要应用之一&#xff0c;用于判断文本的情感倾向&#xff0c;如正面、负面或中性。随着深度学习的发展&#xff0c;预训练语言模型如BERT在各种自然语言处理任务中取得了…
阅读更多...
【C语言】计算3x3矩阵每行的最大值并存入第四列

【C语言】计算3x3矩阵每行的最大值并存入第四列

文章目录 代码解释 代码 #include <stdio.h>int main() {int a[3][4]; // 定义一个3行4列的二维数组int i, j, max;printf("请输入一个3行3列的矩阵&#xff0c;每输入一个元素后按回车键&#xff1a;\n");// 读取用户输入的3x3矩阵for (i 0; i < 3; i) {…
阅读更多...
最新文章

Copyright @ 2022~2023