本文主要是介绍Day44- 动态规划part12，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、买卖股票的最佳时机含冷冻期
题目一：309. 买卖股票的最佳时机含冷冻期
309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
定义三种状态来表示每天结束时可能的持有状态：
hold[i]：在第i天结束时，持有一支股票所得到的最大利润。notHold[i]：在第i天结束时，不持有任何股票，并且处于冷冻期的最大利润。free[i]：在第i天结束时，不持有任何股票，并且不处于冷冻期的最大利润。对于
hold[i]，有两种情况：
- 从
i-1天就持有股票转移过来，即hold[i-1]；- 在第
i天买入股票，那么第i-1天不能是冷冻期，即free[i-1] - prices[i]。对于
notHold[i]，只有一种情况：
- 在第
i天卖出股票，即hold[i-1] + prices[i]。对于
free[i]，有两种情况：
- 第
i-1天就已经是自由状态，即free[i-1]；- 第
i-1天是冷冻期，即notHold[i-1]。初始条件：
hold[0] = -prices[0]，因为第一天买入股票。notHold[0] = 0，第一天不可能卖出股票。free[0] = 0，第一天没有进行任何操作。
/** @lc app=leetcode.cn id=309 lang=cpp** [309] 买卖股票的最佳时机含冷冻期*/// @lc code=start
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n <= 1) return 0;vector<int> hold(n, 0), notHold(n, 0), free(n, 0);hold[0] = -prices[0];notHold[0] = 0;free[0] = 0;for (int i = 1; i < n; ++i) {hold[i] = max(hold[i-1], free[i-1] - prices[i]);notHold[i] = hold[i-1] + prices[i];free[i] = max(free[i-1], notHold[i-1]);}return max(notHold[n-1], free[n-1]);}
};
// @lc code=end二、买卖股票的最佳时机含手续费
题目一：309. 买卖股票的最佳时机含手续费
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
考虑到每次交易都需要支付手续费，可以定义两种状态：
hold[i]：表示在第i天结束时持有股票的最大利润。notHold[i]：表示在第i天结束时不持有股票的最大利润。对于
hold[i]和notHold[i]，有以下状态转移方程：
hold[i]可以由两个状态转换而来：
hold[i-1]：表示第i-1天就持有股票，第i天继续持有。notHold[i-1] - prices[i]：表示第i-1天不持有股票，第i天买入股票，因此利润要减去第i天的股票价格。
notHold[i]也可以由两个状态转换而来：
notHold[i-1]：表示第i-1天不持有股票，第i天继续不持有。hold[i-1] + prices[i] - fee：表示第i-1天持有股票，第i天卖出股票，因此利润要加上第i天的股票价格并减去手续费。初始条件如下：
hold[0] = -prices[0]：因为如果第一天买入股票，利润就是负的股票价格。notHold[0] = 0：因为如果第一天不进行任何操作，利润为0。
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();vector<int> hold(n, 0), notHold(n, 0);hold[0] = -prices[0];notHold[0] = 0;for (int i = 1; i < n; ++i) {hold[i] = max(hold[i-1], notHold[i-1] - prices[i]);notHold[i] = max(notHold[i-1], hold[i-1] + prices[i] - fee);}return notHold[n-1];}
};
这篇关于Day44- 动态规划part12的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
