动态规划之简单多状态 dp 问题
01.买卖股票的最佳时机含冷冻期02.买卖股票的最佳时机含手续费03.买卖股票的最佳时机 III04.买卖股票的最佳时机 IV
01.买卖股票的最佳时机含冷冻期
题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
给定一个整数数组prices,其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示:
1 <= prices.length <= 50000 <= prices[i] <= 1000
思路
状态表表示:
对于线性动态规划,我们使用“经验+题目要求”方式定义状态表。在这里,我们选择以某个位置为结尾的方式,并考虑了三个状态:买入、可交易和冷冻期。用三个数组表示这些状态:
dp[i][0]:第 i 天结束后,处于“买入”状态的最大利润。dp[i][1]:第 i 天结束后,处于“可交易”状态的最大利润。dp[i][2]:第 i 天结束后,处于“冷冻期”状态的最大利润。 状态转移方程:
根据规则: i. 处于“买入”状态时,可以继续持有股票或卖出股票。 ii. 处于“卖出”状态时,需要考虑是否在冷冻期。对于 dp[i][0],有两种情况可达到这个状态: i. 在 i-1 天持有股票,此时最大收益应与 i-1 天相同:dp[i-1][0]。 ii. 在 i 天买入股票,选择 i-1 天不在冷冻期买入,最大收益为:dp[i-1][1] - prices[i]。 综合两种情况取最大值:dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])。对于 dp[i][1],有两种情况可达到这个状态: i. 在 i-1 天处于冷冻期,对应状态为:dp[i-1][2]。 ii. 在 i-1 天没有股票,不在冷冻期,对应状态为:dp[i-1][1]。 综合两种情况取最大值:dp[i][1] = max(dp[i-1][1], dp[i-1][2])。对于 dp[i][2],只有一种情况可达到这个状态:在 i-1 天卖出股票,对应状态转移为:dp[i][2] = dp[i-1][0] + prices[i]。 初始化:
由于每个状态都依赖于前一个位置的值,需要初始化每一行的第一个位置:
dp[0][0]:初始为购买第一天的股票,设为负股价:-prices[0]。dp[0][1]:初始为无操作,设为0。dp[0][2]:初始为无股票,即冷冻期,设为0。 填表顺序:
根据状态表表示,从左往右依次填充三个表格。 返回值:
返回卖出状态下的最大值,即 max(dp[n-1][1], dp[n-1][2])。
代码
class Solution {
public:
int maxProfit(vector
int n=prices.size();
vector
dp[0][0]=-prices[0];
for(int i=1;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][2]); dp[i][2]=dp[i-1][0]+prices[i]; } return max(dp[n-1][1],dp[n-1][2]); } }; 02.买卖股票的最佳时机含手续费 题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ 给定一个整数数组 prices,其中 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 提示: 1 <= prices.length <= 5 * 1041 <= prices[i] < 5 * 1040 <= fee < 5 * 104 思路 状态表表示: 对于线性动态规划,我们采用“经验+题目要求”的方式定义状态表。在这里,我们选择以某个位置为结尾的方式,结合题目要求,定义了两个状态数组: f[i] 表示第 i 天结束后,处于“买入”状态的最大利润。g[i] 表示第 i 天结束后,处于“卖出”状态的最大利润。 状态转移方程: 在选择在“卖出”状态支付手续费的情况下,可以简化为在“买入”状态时不考虑手续费问题。对于 f[i],有两种情况可达到这个状态: i. 在 i-1 天持有股票,第 i 天啥也不做,最大收益为 f[i-1]。 ii. 在 i-1 天没有股票,在第 i 天买入股票,最大收益为 g[i-1] - prices[i]。 综合两种情况取最大值:f[i] = max(f[i-1], g[i-1] - prices[i])。对于 g[i],有两种情况可达到这个状态: i. 在 i-1 天持有股票,在第 i 天将股票卖出,最大收益为 f[i-1] + prices[i] - fee。 ii. 在 i-1 天没有股票,第 i 天啥也不做,最大收益为 g[i-1]。 综合两种情况取最大值:g[i] = max(g[i-1], f[i-1] + prices[i] - fee)。 初始化: 由于需要使用前一个状态,初始化第一个位置: f[0] 处于“买入”状态,初始化为 -prices[0]。g[0] 处于“没有股票”状态,初始化为 0。 填表顺序: 从左往右填充两个表格。 返回值: 返回“卖出”状态下最后一天的最大值收益:g[n - 1]。 代码 class Solution { public: int maxProfit(vector int n=prices.size(); vector vector f[0]=-prices[0]; for(int i=1;i { f[i]=max(f[i-1],g[i-1]-prices[i]); g[i]=max(g[i-1],f[i-1]+prices[i]-fee); } return g[n-1]; } }; 03.买卖股票的最佳时机 III 题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 **注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入:prices = [3,3,5,0,0,3,1,4] 输出:6 解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。 随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 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。 示例 4: 输入:prices = [1] 输出:0 提示: 1 <= prices.length <= 1050 <= prices[i] <= 105 思路 状态表示: 使用「经验 + 题目要求」定义线性动态规划的状态表示。选择以某个位置为结尾的方式,结合题目要求,定义状态表示。使用两个数组表示「买入」和「可交易」两个状态,并加上一维表示交易次数。定义 f[i][j] 表示第 i 天结束后,完成了 j 次交易,处于「买入」状态的最大利润;g[i][j] 表示第 i 天结束后,完成了 j 次交易,处于「卖出」状态的最大利润。 状态转移方程: 对于 f[i][j],有两种情况:在 i-1 天交易了 j 次且处于「买入」状态,或在 i-1 天交易了 j 次且处于「卖出」状态。取两者的最大值。对于 g[i][j],有两种情况:在 i-1 天交易了 j 次且处于「卖出」状态,或在 i-1 天交易了 j-1 次且处于「买入」状态。同样取两者的最大值,但需要判断 j 是否大于等于 1。 初始化: 初始化第一行,考虑第 0 天只能处于「买入过一次」状态的情况,设置 f[0][0] 为 -prices[0],其余状态为 -INF(防止减法发生越界的常用手段)。 填表顺序: 从上往下每一行,从左往右填充状态表。 返回值: 返回处于「卖出状态」的最大值,即 g 表的最后一行的最大值。 代码 class Solution { const int INF = 0x3f3f3f3f; public: int maxProfit(vector int n=prices.size(); vector vector f[0][0]=-prices[0],g[0][0]=0; for(int i=1;i for(int j=0;j<3;++j){ f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]); g[i][j]=g[i-1][j]; if(j>0) g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]); } return max(g[n-1][0],max(g[n-1][1],g[n-1][2])); } }; 04.买卖股票的最佳时机 IV 题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/ 给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。 **注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入:k = 2, prices = [2,4,1] 输出:2 解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。 示例 2: 输入:k = 2, prices = [3,2,6,5,0,3] 输出:7 解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。 提示: 1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000 思路 这里和上一题最大的区别就是交易次数的限制,需要注意的是,k值可能超过数组长度的一半,所以我们需要注意k的取值,其余同上一题的原理。 代码 class Solution { const int INF = 0x3f3f3f3f; public: int maxProfit(int k, vector int n=prices.size(); k=min(k,n/2); vector vector f[0][0]=-prices[0],g[0][0]=0; for(int i=1;i for(int j=0;j<=k;++j){ f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]); g[i][j]=g[i-1][j]; if(j>0) g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]); } int ret = 0; for(int i=0;i<=k;++i) ret=max(ret,g[n-1][i]); return ret; } }; 好文推荐
发表评论