首页 > 其他分享 >代码随想录训练营day41|121. 买卖股票的最佳时机,122.买卖股票的最佳时机II,123.买卖股票的最佳时机III

代码随想录训练营day41|121. 买卖股票的最佳时机,122.买卖股票的最佳时机II,123.买卖股票的最佳时机III

时间:2024-09-10 19:49:33浏览次数:15  
标签:买卖 股票 最佳时机 max prices dp size

121. 买卖股票的最佳时机

这题和贪心中的买股票很想,但这里不用考虑局部问题,因为只用买一张卖一张。
我想可以用一个数组dp来记录买入价格和卖出价格。
然后遍历数组
草我感觉我写的想贪心。

动态规划

dp[i][0]表示第i天不持股的最大收益,dp[i][1]表示第i天持股的最大收益。dp[i][1]实际上是负数,因为股票还没卖出去。

dp[i][0]可以由由dp[i-1][1]+prices[i]推到而来,也可以是dp[i-1][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][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            //不持有股票的话要么延续前一天的状态,要么是当天卖掉了
            dp[i][1]=max(dp[i-1][1],-prices[i]);
            //要么是延续前一天持股的状态,要么是才买入。
            //由于股票只能买一次,所以并不用考虑前面没有持股的状态。
        }
        return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);
    }
};

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

唯一的区别就是在第i天持有股票时,可以是直接继承[i-1][1],还能是当天买入,在上一题中,由于只能买一次,所以买入时手上的最大利润是0,0-prices[i],但这题可以买卖多次,变成了dp[i-1][0]-prices[i]

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

变成了最多买卖两只股票,且不能同时拥有两只。

变成五个状态了
0:不操作
1:第一次持有股票。
2:第一次有股票后不持有股票。
3:第二次有股票。
4:第二次有股票后不持有股票
注意第一天的股票也要初始化dp[0][3]

 dp[0][1]=-prices[0];
        dp[0][3]=-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][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 max(dp[prices.size()-1][2],dp[prices.size()-1][4]);

标签:买卖,股票,最佳时机,max,prices,dp,size
From: https://blog.csdn.net/wwwgxd/article/details/142100260

相关文章

  • 买卖股票的最佳时机含冷冻期
    题目描述给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格。​设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):卖出股票后,你无法在第二天买入股票(即冷冻期为1天)。注意:你不能同时参与多笔交易(你......
  • 24暑假算法刷题 | Day41 | 动态规划 IX | LeetCode 188. 买卖股票的最佳时机 IV,309.
    目录188.买卖股票的最佳时机IV题目描述题解309.买卖股票的最佳时机含冷冻期题目描述题解714.买卖股票的最佳时机含手续费题目描述题解188.买卖股票的最佳时机IV点此跳转题目链接题目描述给你一个整数数组prices和一个整数k,其中prices[i]是某支给定......
  • 股票问题
    121题给定一个数组prices,其中prices[i]是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。但是,你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。示例输入:prices=[7,1,5,3,6,4]输出:5解释:在......
  • 【2024年Python量化分析】为股票数据量化分析最新整理的免费获取股票实时行情数据API
    ​最近一两年,股票量化分析越来越火了,想入门这行,首先得搞定股票数据。毕竟,所有量化分析都是靠数据说话的,实时交易、历史交易、财务、基本面,这些数据咱们都得有。咱们的目标就是把这些数据里的金子挖出来,指导咱们的投资策略。​为了找数据,我可是没少折腾,自己动手写过网易、......
  • 用RNN(循环神经网络)预测股票价格
    RNN(循环神经网络)是一种特殊类型的神经网络,它能够处理序列数据,并且具有记忆先前信息的能力。这种网络结构特别适合于处理时间序列数据、文本、语音等具有时间依赖性的问题。RNN的核心特点是它可以捕捉时间序列中的长期依赖关系。RNN的基本结构RNN由多个重复的单元组成,每个单元......
  • 714. 买卖股票的最佳时机含手续费(leetcode)
    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/classSolution{publicintmaxProfit(int[]prices,intfee){//f[i][j]表示前i天进行交易购买,j=0表示持有股票,j=1表示未持有股票,划分两个状态//f[i][0]=......
  • [HarmonyOS Next示例代码]一多股票类的关键场景实现
    MultiTicketClass:本示例主要使用栅格布局和List组件相结合的方式,实现了股票类差异化的多场景响应式变化效果。HarmonyOS next示例代码全集一多股票类的关键场景实现介绍本示例主要使用栅格布局和List组件相结合的方式,实现了股票类差异化的多场景响应式变化效果。效果......
  • 通过联立方程模型来评估货币政策对股票市场的影响
    一:联立方程模型的介绍联立方程模型在金融数据中的应用主要是为了分析和估计经济变量之间的相互关系和影响。在金融领域,这些模型可以帮助理解不同金融变量(如股票价格、货币供应量、利率等)之间的动态关系。联立方程模型通常包含内生变量和外生变量。内生变量是由模型系统内部的......
  • Python量化交易股票投资,是百战百胜的吗
    Python股票接口实现查询账户,提交订单,自动交易(1)Python股票程序交易接口查账,提交订单,自动交易(2)炒股真有百战百胜之法?在充满变数的股票市场中,许多投资者都梦寐以求一种能够百战百胜的炒股方法。现实真的如此理想吗?K线图的奥秘K线图的构成与意义K线图由开盘价、收盘价......
  • 程序设计—基于网络爬虫的股票价格分析系统 项目源码27486
    摘 要在21世纪信息时代,随着网络技术的飞速发展和大数据时代的到来,股票价格分析对于投资者和金融机构的重要性日益凸显。传统的股票价格分析方法往往依赖于人工收集和整理数据,效率低下且易出错。因此,开发一套基于网络爬虫的股票价格分析系统变得至关重要。本文旨在探讨基于......