正文

动态规划股票交易(代码片段)

桃陉  桃陉  2022-12-13  529

关键词：

文章目录

1.买卖股票的最佳时机

1.1 题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

$\\bullet$ 1 <= prices.length <= 105
$\\bullet$ 0 <= prices[i] <= 104

来源：力扣（LeetCode）
链接：题目来源

1.2 分析

$\\bullet$ 我们只需要进行一次交易，即买入一次卖出一次。当数组中只有一个数字时返回0，当数组中数字倒序时无法买卖返回0。

$\\bullet$ 在编写时我们需要一个变量ans来指向第一个数字（ans表示买入的时刻，我们要保证它尽量的小），然后从下标为1的地方遍历数组，当遍历元素小于ans时，我们就更新ans。每次都将最终返回结果res与当前元素减去ans的值进行比较，取其中较大的值。
$r e s = m a x (r e s, p r i c e s [i] - a n s);$

1.3 代码

class Solution 
public:
    int maxProfit(vector<int>& prices) 
        int n=prices.size();
        int ans=prices[0],res=0;
        for(int i=1;i<n;i++)
        
            if(prices[i]<ans) ans=prices[i];
            res=max(res,prices[i]-ans);  
        
        return res;

    
;

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

2.1 题目

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

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

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

$\\bullet$ 1 <= prices.length <= 3 * 104
$\\bullet$ 0 <= prices[i] <= 104

来源：力扣（LeetCode）
链接：题目来源

2.2 分析

$\\bullet$ 我们注意到与第一问不同，这次可以多次的买入与卖出，然后找到最大的利润。

$\\bullet$ 在这里我们需要设置两个状态，dp[i][0] 表示当前不持有股票，dp[i][1] 表示当前持有股票。那么最后返回dp[n-1][0]。

$\\bullet$ 对于dp[i][0] 来说，可能昨天也不持有（dp[i-1][0]）或者昨天持有今天卖出(dp[i-1][1]+prices[i])，取两者的较大值。
$d p [i - 1] [0] = m a x (d p [i - 1] [0], d p [i - 1] [1] + p r i c e s [i]);$

$\\bullet$ 对于dp[i][1] 来说，可能昨天也持有（dp[i-1][1]）或者昨天不持有今天买入(dp[i-1][0]-prices[i])，取两者的较大值。
$d p [i - 1] [1] = m a x (d p [i - 1] [1], d p [i - 1] [0] - p r i c e s [i]);$

2.3 代码

class Solution 
public:
    int maxProfit(vector<int>& prices) 
        int n=prices.size();
        if(n==1) return 0;
        //dp[i][0]表示当前不持有股票，dp[i][1]表示当前持有股票
        vector<vector<int>>dp(n,vector<int>(2,0));
        dp[0][1]=-prices[0];
        for(int i=1;i<n;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[n-1][0];
    
;

3.最佳买卖股票时机含冷冻期

3.1 题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

来源：力扣（LeetCode）
链接：题目来源

3.2 分析

$\\bullet$ 本题相对于上一题增加了一个冷冻期，此时持有股票的状态得分成两部分，一个为今天持有股票且不卖出（dp[i][0]），一个为今天持有且今天卖出（明天为冷冻期）（dp[i][1]）。不持有股票的状态不变（dp[i][2]）。最后返回 max(dp[n-1][1],dp[n-1][2]);

$\\bullet$ 对于dp[i][0]来说，可能昨天也持有（dp[i-1][0]）或者昨天不持有今天买入(dp[i-1][2]-prices[i])，取二者较大值。
$d p [i] [0] = m a x (d p [i - 1] [0], d p [i - 1] [2] - p r i c e s [i]);$

$\\bullet$ 对于dp[i][1]来说，昨天必须持有股票今天才可以卖出。
$d p [i] [1] = d p [i - 1] [0] + p r i c e s [i];$

$\\bullet$ 对于dp[i][2]来说，可能昨天也不持有股票（dp[i-1][2]）或者昨天持有并卖出(dp[i-1][1])，取二者较大值。
$d p [i] [2] = m a x (d p [i - 1] [2], d p [i - 1] [1]);$

3.3 代码

class Solution 
public:
    int maxProfit(vector<int>& prices) 
        int n=prices.size();
        if(n==0) return 0;
        /*
        dp[i][0] 表示当天持有一支股票
        dp[i][1] 表示当天卖出股票（意思就是第i+1天是冷冻期）
        dp[i][2] 表示当天不持有股票
        */
        vector<vector<int>>dp(n,vector<int>(3,0));
        dp[0][0]=-prices[0];

        for(int i=1;i<n;i++)
        
            dp[i][0]= max(dp[i-1][0],dp[i-1][2]-prices[i]); //可能是昨天就持有或者昨天不持有今天买入
            dp[i][1]=dp[i-1][0]+prices[i]; //昨天必须持有今天才可以卖出
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]);
        
        return max(dp[n-1][1],dp[n-1][2]);
    
;

4.买卖股票的最佳时机含手续费

4.1 题目

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

$\\bullet$ 1 <= prices.length <= 5 * 104
$\\bullet$ 1 <= prices[i] < 5 * 104
$\\bullet$ 0 <= fee < 5 * 104

来源：力扣（LeetCode）
链接：题目来源

4.2 分析

$\\bullet$ 本题其实与第二题十分相似，只是在卖出的基础上添加了小费，所以我们只需要在每次卖出的基础上补充小费即可。

$\\bullet$ 同样设置两个状态，dp[i][0] 表示当前不持有股票，dp[i][1] 表示当前持有股票。那么最后返回dp[n-1][0]。

$\\bullet$ dp[i][1] 不变，对于dp[i][0]加上小费fee。
$d p [i] [0] = m a x (d p [i - 1] [0], d p [i - 1] [1] + p r i c e s [i] - f e e);$

4.3 代码

class Solution 
public:
    int maxProfit(vector<int>& prices, int fee) 
        int n=prices.size();
        if(n==1) return 0;
        //dp[i][0]表示当前不持有股票，dp[i][1]表示当前持有股票
        vector<vector<int>>dp(n,vector<int>(2,0));
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++)
        
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        
        return dp[n-1][查看详情  
                
[bzoj1855][scoi2010]股票交易_动态规划_单调队列
...系列++...题目链接注释：略。想法：这个题还是挺难的。动态规划没跑了状态：dp[i][j]表示第i天手里有j个股票的最大获利。转移：第i天可以选择搞事情或者什么都不干。如果不买不卖的话，有dp[i][j]=dp[i-1][j]如果选择买入，dp[i][j...  查看详情  
                
leetcode122.买卖股票的最优时机ii(代码片段)
LeetCode122.买卖股票的最佳时机II题目描述思路描述动态规划贪心题目描述给定一个数组prices，其中prices[i]是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次...  查看详情  
                
动态规划总结(代码片段)
 给定一个整数数组nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入:[-2,1,-3,4,-1,2,1,-5,4],输出:6解释: 连续子数组 [4,-1,2,1]的和最大，为 6。f(k)表示连续以下标为k...  查看详情  
                
动态规划(代码片段)
动态规划121.买卖股票的最佳时机647.回文子串5.最长回文串46.全排列找出字符串的最小的编辑距离213.打家劫舍II121.买卖股票的最佳时机publicstaticintmaxProfit(int[]prices)intmin=prices[0];intres=0;intlen=prices.length;for(inti=0;i<len;i...  查看详情  
                
352买卖股票的good时机和最大子数组（todo，动态规划）(代码片段)
一、题目给定一个数组prices，它的第 i个元素 prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回...  查看详情  
                
leetcodeno.188买卖股票的最佳时机iv（动态规划）
一、题目描述给定一个整数数组 prices，它的第i个元素 prices[i]是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。注意：你不能同时参与多笔交易（你必须在再次购买...  查看详情  
                
leetcodeno.188买卖股票的最佳时机iv（动态规划）
一、题目描述给定一个整数数组 prices，它的第i个元素 prices[i]是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。注意：你不能同时参与多笔交易（你必须在再次购买...  查看详情  
                
java求解买卖股票的xx时机含手续费(代码片段)
...手续费文章目录一、题目二、题解三、代码四、总结五、动态规划解法一、题目给定一个整数数组prices，其中第i个元素代表了第i天的股票价格；整数fee代表了交易股票的手续费用。你可以无限次地完成交易，但是你...  查看详情  
                
leetcode309最佳买卖股票时机含冷冻期（动态规划）(代码片段)
又是一道找到了状态转移方程，就可以迎刃而解的问题但是状态转移方程不好找啊分析题目：每一天的四种状态：买进、卖出、冷冻期、什么都不做每天的状态排列遵循：买...卖冷...买...卖冷... 其中...代表什么都不做的日子...  查看详情  
                
p2569股票交易(代码片段)
...减去买入的钱数。收益并不是只增不减。可以想到的是：动态规  查看详情  
                
arts第五周(代码片段)
...列的最后一题，也是难度最大的一题。这里我们用标准的动态规划算法来解这道题，既然是用动态规划的办法，那就要先定义出动态规划的状态和状态转移方程。状态：根据题意，我们需要定义个三维的状态，分别是：天数,交...  查看详情  
                
leetcode刷题笔记-动态规划-day7(代码片段)
文章目录LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目2.解题思路3.代码121.买卖股票的最佳时机1.题目2.解题思路3.代码122.买卖股票的最佳时机II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目原...  查看详情  
                
leetcode刷题笔记-动态规划-day7(代码片段)
文章目录LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目2.解题思路3.代码121.买卖股票的最佳时机1.题目2.解题思路3.代码122.买卖股票的最佳时机II1.题目2.解题思路3.代码LeetCode刷题笔记-动态规划-day71014.最佳观光组合1.题目原...  查看详情  
                
[算法]股票问题(代码片段)
...释:在这种情况下,没有交易完成,所以最大利润为0。思路动态规划。前i天的最大收益=max前i-1天的最大收益，第i天的价格-前i-1天中的最小价格代码importsysclassSolution:defmaxProfit(self,prices):""":typeprices:List[int]:rtype:int"""max_p,min_p=0,sys.maxsi...  查看详情  
                
聊聊买卖股票的最佳时机(代码片段)
...大赛哥，好久不见，天天想念！最近梳理高频动态规划问题，股票问题当然是非常经典的动态规划问题，并且整个系列有好几道题，这里我整理了6道股票系列的经典问题分享给大家，咱们今天聊聊买卖...  查看详情  
                
聊聊买卖股票的最佳时机(代码片段)
...大赛哥，好久不见，天天想念！最近梳理高频动态规划问题，股票问题当然是非常经典的动态规划问题，并且整个系列有好几道题，这里我整理了6道股票系列的经典问题分享给大家，咱们今天聊聊买卖...  查看详情  
                
123买卖股票的最佳时机iii(代码片段)
...e-to-buy-and-sell-stock-iii法一：参考别人自己写的代码思路：动态规划，首先题中有两个变量，股票在第几天卖出和卖出的次数，dp[i][j]表示第i天卖出j次股票后的最大利润，状态转移方程：a=max([prices[row]-prices[j]+dp[j][col-1]forjinrange(0,r...  查看详情



      
        
          免责声明：如内容涉及版权或违规等问题，请在尽快内联系我们pp114#vip.qq.com，我们将在第一时间删除内容。