软件项目管理方案_动漫设计难不难学_自己有网站怎么推广_世界杯32强排名

在这里插入图片描述
下面是将你提供的代码整理成一篇Markdown格式的博客内容：

股票买卖的最大利润

问题描述

给定一个整数数组 prices，其中 prices[i] 是股票在第 i 天的价格。你可以选择在某一天买入股票，并在之后的某一天卖出股票。要求计算出你能够获得的最大利润。

注意：

你不能在买入股票之前卖出股票。
每次交易只能进行一次买入和一次卖出。

思路分析

这个问题可以通过动态规划来求解。我们可以通过递归来模拟每一天的状态，包括是否持有股票，进而找到最大利润。

代码实现

from typing import List
from functools import cache
from math import infclass Solution:def maxProfit(self, prices: List[int]) -> int:n = len(prices)@cache# i为当前天数，fold为当前是否持有股票（True表示持有，False表示不持有）def dfs(i, fold):if i < 0:# 如果当前是持有股票并且i表示的价格是负值，返回负无穷，表示该状态无效return -inf if fold else 0if fold:# 当前持有股票，可以选择：# 1. 继续持有，状态不变# 2. 卖出股票，获得利润return max(dfs(i-1, True), dfs(i-1, False) - prices[i])else:# 当前不持有股票，可以选择：# 1. 继续不持有股票，状态不变# 2. 买入股票，支付价格return max(dfs(i-1, False), dfs(i-1, True) + prices[i])return dfs(n-1, False)  # 从最后一天开始，如果最后没有卖出股票，肯定无法获得最大利润

代码解释

递归函数 dfs(i, fold)：
- i：当前的天数（从0到n-1），表示考虑第 i 天的股票操作。
- fold：表示当前是否持有股票。如果 fold 为 True，则表示持有股票；如果 fold 为 False，则表示不持有股票。
递归终止条件：
- 当 i < 0 时，表示所有的天数都已经考虑完毕，如果当前持有股票，则返回 -inf（不可能的情况），否则返回0（没有任何利润）。
状态转移：
- 如果当前持有股票（fold=True），可以选择继续持有或者卖出：
  - 继续持有：dfs(i-1, True)
  - 卖出股票：dfs(i-1, False) - prices[i]
- 如果当前不持有股票（fold=False），可以选择继续不持有或者买入：
  - 继续不持有：dfs(i-1, False)
  - 买入股票：dfs(i-1, True) + prices[i]
最终返回结果：
- 从最后一天开始进行推导，最终返回的是从 0 到 n-1 这段时间内，最多能够获得的利润。

时间复杂度

由于我们使用了 @cache 装饰器来缓存每次递归的结果，避免了重复计算，因此时间复杂度为 O(n)，其中 n 是股票价格数组的长度。

空间复杂度

由于递归调用栈的深度为 O(n)，并且缓存空间也是 O(n)，所以空间复杂度为 O(n)。

总结

这段代码通过递归与动态规划的结合，实现了股票买卖问题的最优解。通过 @cache 装饰器来缓存每次递归计算的结果，避免了重复计算，从而提高了效率。

class Solution:def maxProfit(self, prices: List[int]) -> int:n=len(prices)@cache#i为当前到哪个位置,flod是当前是否持有def dfs(i,fold):if i<0:#如果当前是持有的但是i代表的price是负值那么就是返回负无穷代表一定不选这个状态return -inf if fold else 0if fold:#如果这次是持有的，那么上次肯定是持有的或者上次的没持有但是买了取极大值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)#因为是反向推 所以直接从最后一个N-1开始就好，如果最后没有卖出去肯定不是赚钱最多的，只留这个