买股票动态规划问题

约 2091 字大约 7 分钟

2024-12-07

买股票最佳时期Ⅱ

给你一个整数数组 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。
最大总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。\

这题可以考虑用动态规划，即当天的最大利润是通过前一天来获得的。
假设当前是第 $i$ 天，那么第 $i$ 天的结束时的利润怎么来，很容易想到：
第i天结束时的利润 = 第 $0$ 到 $i-1$ 天的利润 + 第 $i$ 天产生的利润。这样可以递推下去。
那么第 $i$ 天的利润如何计算，如果什么都不做利润为 $0$ ，买入股票利润为 $-prices[i]$ ，卖出股票利润为 $prices[i]$ 。注意这里考虑卖出并没有考虑买入的价格，因为买入的价格产生的利润，会在前面计算（表现在前面计算的 $-prices[i]$ 上）。
他的子问题那么可以递归到第 $i-1$ 天的利润最大值。
我们给出状态方程：
$dfs(i,0) = max( dfs(i - 1,0) , dfs(i - 1,1) + prices[i] )$
$dfs(i,1) = max( dfs(i - 1,1) , dfs(i - 1,0) - prices[i] )$
那么递归边界条件是什么：
$dfs(-1,0) = 0$ 第0天开始未持有股票利润为0
$dfs(-1,1) = -\infty$ 第0天开始不可能持有股票
那么动态规划中，只需要保留两个参数，一个是第 $i$ 天，另一个是买入还是卖出还是什么都不做。另外最后一天是必须要卖出的。下面看代码

Python

class Solution:
		def maxProfit(self, prices: List[int]) -> int:
				n = len(prices)
				@cache  #缓存装饰器，避免重复计算 dfs 的结果
				# true 代表可以买入的状态，
				# false 代表不能买入的状态也就是卖出的状态
				# 通过这个表达买进卖出和什么都不做的三种状态
				def dfs(i: int, hold: bool) -> int:
						if i < 0:
								return -inf if hold else 0
						if hold:
								return max(dfs(i - 1, True),dfs(i - 1, False) - prices[i])
						return max(dfs(i - 1, False), dfs(i - 1, True) + prices[i])
				return dfs(n - 1, False)

C++

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int n = prices.size();
		vector<vector<int>> visited(
		n,vector<int>(2, -1));
		function<int(int, int)> dfs = [&](int i, int hold) -> int {
			// 1 代表可以买入的状态，
			// 0 代表不能买入的状态也就是卖出的状态
			// 通过这个表达买进卖出和什么都不做的三种状态
			if (i < 0)
			return hold == 0 ? 0 : INT_MIN / 2;
			auto& res = visited[i][hold];//记忆化搜索，避免重复计算dfs的结果
			if (visited[i][hold] != -1)
				return visited[i][hold];

			if (hold == 1) {
				return res = max(dfs(i - 1, 1),#什么都不做
					dfs(i - 1, 0) - prices[i]);#买入股票
			}
			return res = max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
		};
		return dfs(n - 1,  0);
	}
};

具体分析一下代码，从划分子问题开始。如果当天的状态是可以买入，那么当天可以做出的选择是买出股票，或者什么都不做，二者取最大值。对应Python代码中第10行的内容。如果当天状态是可以卖出，那么当天也是两种选择，卖出股票或者什么都不做。对应Python代码其14行的内容。

注意

在买入和卖出股票的时候，记得修改状态。

提示

动态规划代码，一般先写边界条件，同时这是最容易出问题的。第0天开始，不持有股票，利润初始化为0.持有股票这个是不可能的状态定义为负无穷。然后是分解子问题。

2.买卖股票问题Ⅲ

这题与上题的区别是，你可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。那么和上体相比，需要引入参数 $j$ 来代表当前完成第几笔交易。在卖出股票和买入股票的时候修改 $j$ 。前面的思路是类似的，关键是怎么样修改 $j$ 的值。我们可以统一规定在卖出或者买入的时候减，这样可以避免了重复计算。那么我们现在规定统一在买入股票的时候减。下面给出状态方程：
$dfs(i,,j,0) = max( dfs(i - 1,j,0) , dfs(i - 1,j,1) + prices[i] )$
$dfs(i,,j,1) = max( dfs(i - 1,j,1) , dfs(i - 1,j-1,0) - prices[i] )$
那么递归边界和初始状态是什么呢：
$dfs(.,-1,.) = -\infty$ 任何清空下， $j$ 都不能为负，也就是不能超过股票交易次数。
$dfs(-1,j,0) = 0$ 第0天开始未持有股票利润为0
$dfs(-1,j,1) = -\infty$ 第0天开始不可能持有股票
下面给出代码：

Python

class Solution:
		def maxProfit(self, prices: List[int]) -> int:
				n = len(prices)
				@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
				def dfs(i: int, j: int, hold: bool) -> int:
						if j < 0:
								return -inf
						if i < 0:
								return -inf if hold else 0
						if hold:
								return max(dfs(i - 1, j, True), 
									dfs(i - 1, j - 1, False) - prices[i])
						return max(dfs(i - 1, j, False), 
									dfs(i - 1, j, True) + prices[i])
				return dfs(n - 1, 2, False)

C++

#include <iostream>
class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int n = prices.size();
		vector<vector<vector<int>>> visited(
			n, vector<vector<int>>(k+1, vector<int>(2, -1)));

		function<int(int, int, int)> dfs = [&](int i, int j, int hold) -> int {
			if (j < 0)
				return INT_MIN / 2;
			if (i < 0)
				return hold == 0 ? 0 : INT_MIN / 2;
			auto& res = visited[i][j][hold];
			if (visited[i][j][hold] != -1)
			eturn visited[i][j][hold];

			if (hold == 1) {
				return res = max(dfs(i - 1, j, 1),
						dfs(i - 1, j - 1, 0) - prices[i]);
			}
			return res = max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i]);
		};
		return dfs(n - 1, 2, 0);
	}
};

3.买股票最近时期Ⅲ

这题其实是上题的一搬形式，思路照搬。状态转移方程也可以照搬
$dfs(i,,j,0) = max( dfs(i - 1,j,0) , dfs(i - 1,j,1) + prices[i] )$
$dfs(i,,j,1) = max( dfs(i - 1,j,1) , dfs(i - 1,j-1,0) - prices[i] )$
那么递归边界和初始状态是什么呢：
$dfs(.,-1,.) = -\infty$ 任何清空下， $j$ 都不能为负，也就是不能超过股票交易次数。
$dfs(-1,j,0) = 0$ 第0天开始未持有股票利润为0
$dfs(-1,j,1) = -\infty$ 第0天开始不可能持有股票
下面来看代码：\

Python

class Solution:
		def maxProfit(self, k: int,prices: List[int]) -> int:
				n = len(prices)
				@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
				def dfs(i: int, j: int, hold: bool) -> int:
						if j < 0:
								return -inf
						if i < 0:
								return -inf if hold else 0
						if hold:
								return max(dfs(i - 1, j, True), 
									dfs(i - 1, j - 1, False) - prices[i])
						return max(dfs(i - 1, j, False), 
									dfs(i - 1, j, True) + prices[i])
				return dfs(n - 1, k, False)

C++

#include <iostream>
class Solution {
public:
	int maxProfit(vector<int>& prices，int k) {
		int n = prices.size();
		vector<vector<vector<int>>> visited(
			n, vector<vector<int>>(k+1, vector<int>(2, -1)));

		function<int(int, int, int)> dfs = [&](int i, int j, int hold) -> int {
			if (j < 0)
				return INT_MIN / 2;
			if (i < 0)
				return hold == 0 ? 0 : INT_MIN / 2;
			auto& res = visited[i][j][hold];
			if (visited[i][j][hold] != -1)
			eturn visited[i][j][hold];

			if (hold == 1) {
				return res = max(dfs(i - 1, j, 1),
						dfs(i - 1, j - 1, 0) - prices[i]);
			}
			return res = max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i]);
		};
		return dfs(n - 1, k, 0);
	}
};

更新日志

2024/12/13 13:22

查看所有更新日志

24fac-prepare interview于 2024/12/13