【专题】股票问题
目录
文章：一个方法团灭 6 道股票问题
121. 买卖股票的最佳时机 (只能买一次)
122. 买卖股票的最佳时机 II (可多次买卖)
123. 买卖股票的最佳时机 III (最多买2次)
188. 买卖股票的最佳时机 IV
309. 最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费
文章：一个方法团灭 6 道股票问题
LeetCode股票题通用方法：一个方法团灭 6 道股票问题
动态规划(三维)：第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（用 1 表示持有，0 表示没有持有）
比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。
121. 买卖股票的最佳时机 (只能买一次)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
【方法1】
/* 找最小谷(minprice)之后的最大峰
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode/
*/
class Solution {
public:int maxProfit(vector& prices) {int minprice = INT_MAX, maxprofit = 0;for(auto price : prices){if(price < minprice)minprice = price;else if(price-minprice > maxprofit)maxprofit = price-minprice;}return maxprofit;}
}; 【方法2：动态规划(通用方法)】
/* 股票题总结：
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
*/
class Solution {
public:int maxProfit(vector& prices) {int n = prices.size();if(n==0) return 0;int dp[n][2]; // dp[i][j]:第i天持有/不持有(j=0/1)股票的利润for(int i=0; i
122. 买卖股票的最佳时机 II (可多次买卖)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
【方法1】贪心。涨就买，跌就卖。
class Solution {
public:int maxProfit(vector& prices) {int maxprofit = 0;for(int i=1; i prices[i-1])maxprofit += (prices[i]-prices[i-1]);return maxprofit;}
}; 【方法2：动态规划(通用方法)】
class Solution {
public:int maxProfit(vector& prices) {int n = prices.size();if(n==0) return 0;int dp[n][2]; // dp[i][j]:第i天持有/不持有(j=0/1)股票的利润for(int i=0; i
123. 买卖股票的最佳时机 III (最多买2次)
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 2笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
/* 动态规划(通用方法) */
class Solution {
public:int maxProfit(vector& prices) {int k = 2;int n = prices.size();if(n==0) return 0;int dp[n][k+1][2]={}; // dp[i][k_][j]:第i天,已经买了k次,当前持有/不持有(j=0/1)股票的最大利润for(int i=0; i
188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。/* 动态规划(通用方法).
注：因为有个样例k=1000000000, 为了避免超时, 这个样例可以用贪心算法
*/
class Solution {
public:int maxProfit(int k, vector& prices) {int n = prices.size();if(n==0) return 0;if(k >= n/2) // 问题退化为贪心问题(可理解为不限交易次数), 可以节省时间return greedy(prices);int dp[n][k+1][2]={}; // dp[i][k_][j]:第i天,已经买了k次,当前持有/不持有(j=0/1)股票的最大利润for(int i=0; i& prices){int max = 0;for(int i = 1; i < prices.size(); ++i) {if(prices[i] > prices[i-1])max += prices[i]-prices[i-1];}return max;}
};
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]// 动态规划(通用方法). 把122题(不限交易次数)状态方程的i-1改成i-2即可
class Solution {
public:int maxProfit(vector& prices) {int n = prices.size();if(n==0) return 0;int dp[n][2]; // dp[i][j]:第i天持有/不持有(j=0/1)股票的利润for(int i=0; i
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
输入: 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.
/* 动态规划(通用方法). 在122(不限交易次数)状态方程中减去手续费
手续费在买或卖时减去都可以, 但要注意i==0也要保持一致
*/
class Solution {
public:int maxProfit(vector& prices, int fee) {int n = prices.size();if(n==0) return 0;int dp[n][2]; // dp[i][j]:第i天持有/不持有(j=0/1)股票的利润for(int i=0; i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！