第一题、152.乘积最大子数组
方法、动态规划
（很妙，我一开始真的是按照最前面的错误思路想的。。）
class Solution:
def maxProduct(self, nums):
# 获取数组的长度
length = len(nums)
# 初始化两个数组，分别记录最大乘积和最小乘积
maxF = [0] * length
minF = [0] * length
# 将maxF和minF数组的初始值设置为nums中的对应值
for i in range(length):
maxF[i] = nums[i]
minF[i] = nums[i]
# 从数组的第二个元素开始，逐步更新maxF和minF数组
for i in range(1, length):
# 更新当前元素的最大乘积
maxF[i] = max(maxF[i - 1] * nums[i], nums[i], minF[i - 1] * nums[i])
# 更新当前元素的最小乘积
minF[i] = min(minF[i - 1] * nums[i], nums[i], maxF[i - 1] * nums[i])
# 初始化结果为maxF数组的第一个值
ans = maxF[0]
# 遍历maxF数组，找到最大值
for i in range(1, length):
ans = max(ans, maxF[i])
# 返回最终的最大乘积
return ans
渐进时间复杂度和渐进空间复杂度都是 O(n)。
疑问：
1、为什么还要再改变初始值？之前一步不是已经都设为0了吗?
# 将maxF和minF数组的初始值设置为nums中的对应值
for i in range(length):
maxF[i] = nums[i]
minF[i] = nums[i]
解答：代码中maxF和minF在初始化时已经全部设为0，然后又通过循环将它们的初始值设置为nums中的对应值。这一操作看似多余，但在实际代码中是有必要的：
①初始化为0的意义：
在Python中，maxF和minF两个数组最初通过[0] * length的方式初始化。这是为了分配一个与nums数组大小相同的数组，但此时数组中的所有元素都是0。
②将初始值设为nums中的对应值：
由于要计算的是最大和最小乘积，而初始的maxF[i]和minF[i]需要反映nums[i]的值，所以必须在循环中将maxF[i]和minF[i]赋值为nums[i]。如果直接使用0，则会导致后续计算错误，特别是当nums[i]为负数或正数时，乘以0会使结果偏离实际值。
③代码逻辑的完整性：
初始化为0只是为了创建数组并确保它有固定的长度，而将maxF[i]和minF[i]设置为nums[i]则是为了确保后续的最大最小值计算能从正确的初始值开始。
简而言之，最初的[0] * length仅仅是用来创建数组的占位符，而真正需要使用的初始值来自于nums数组，所以必须在循环中进行赋值。
优化空间：
由于第 i 个状态只和第 i−1 个状态相关，根据「滚动数组」思想，可以只用两个变量来维护 i−1 时刻的状态，一个维护 fmax ，一个维护 fmin 。
class Solution:
def maxProduct(self, nums):
# 初始化maxF和minF为数组的第一个元素，表示当前的最大和最小乘积
maxF = nums[0]
minF = nums[0]
# 初始化结果为数组的第一个元素
ans = nums[0]
# 获取数组的长度
length = len(nums)
# 从数组的第二个元素开始遍历
for i in range(1, length):
# 记录当前maxF和minF的值，用于后续计算
mx = maxF
mn = minF
# 更新当前的最大乘积，取三者中的最大值：
# 1. 前一个位置的最大乘积乘以当前元素
# 2. 当前元素
# 3. 前一个位置的最小乘积乘以当前元素
maxF = max(mx * nums[i], nums[i], mn * nums[i])
# 更新当前的最小乘积，取三者中的最小值
minF = min(mn * nums[i], nums[i], mx * nums[i])
# 更新结果为当前的最大乘积和之前结果的最大值
ans = max(int(maxF), ans)
# 返回最终的最大乘积
return ans
记 nums 元素个数为 n。
时间复杂度：程序一次循环遍历了 nums，故渐进时间复杂度为 O(n)。
空间复杂度：优化后只使用常数个临时变量作为辅助空间，与 n 无关，故渐进空间复杂度为 O(1)。
第二题、322.零钱兑换
方法一、记忆化搜索
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 使用LRU缓存装饰器，以减少重复计算
@functools.lru_cache(amount)
def dp(rem) -> int:
# 如果剩余金额小于0，返回-1，表示无解
if rem < 0: return -1
# 如果剩余金额为0，返回0，表示不需要再找硬币
if rem == 0: return 0
# 初始化一个较大的数，表示最小硬币数
mini = int(1e9)
# 遍历每个硬币
for coin in self.coins:
# 递归计算减去当前硬币后的剩余金额所需的最小硬币数
res = dp(rem - coin)
# 如果结果有效且小于当前最小值，更新最小值
if res >= 0 and res < mini:
mini = res + 1
# 如果找到的最小硬币数有效，返回该值，否则返回-1表示无解
return mini if mini < int(1e9) else -1
# 将硬币列表存储在类中，方便递归函数调用
self.coins = coins
# 如果金额小于1，直接返回0，因为不需要任何硬币
if amount < 1: return 0
# 调用递归函数计算并返回结果
return dp(amount)
时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。一共需要计算 S 个状态的答案，且每个状态 F(S) 由于上面的记忆化的措施只计算了一次，而计算一个状态的答案需要枚举 n 个面额值，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)，需要额外开一个长为 S 的数组来存储计算出来的答案 F(S) 。
第一次用到：
@functools.lru_cache(amount)
@functools.lru_cache(amount) 是 Python 中用于缓存函数结果的装饰器 lru_cache 的一种使用方式。它可以大幅提高递归函数的执行效率，特别是在动态规划问题中，此行代码实际上就是在实现记忆化搜索。下面是详细解释：
1. functools.lru_cache的作用：
-
LRU缓存：
LRU是 "Least Recently Used" 的缩写，即“最近最少使用”。lru_cache会缓存函数的返回结果，当函数被调用时，如果传入的参数与之前的某次调用相同，lru_cache就会直接返回缓存中的结果，而无需重新计算。 -
缓存机制：
缓存可以减少重复计算，尤其是在递归或动态规划的问题中，某些子问题可能会被多次计算。使用lru_cache可以避免这些重复计算，从而显著提高效率。
2. @functools.lru_cache(amount) 的具体含义：
-
@符号：
在 Python 中，@符号表示装饰器的使用方式。装饰器是一个函数，作用于另一个函数或方法之上，以增强或修改其行为。在这里，@functools.lru_cache(amount)作用于dp(rem)函数，使得这个函数的返回值可以被缓存。 -
参数
amount：
amount是lru_cache的一个可选参数，用于指定缓存的最大容量。这里amount表示缓存可以存储多少个不同的rem参数的计算结果。当缓存达到这个容量时，最久未使用的缓存项会被移除。 -
无参数的情况：
如果不指定amount，即写作@functools.lru_cache()，则缓存的容量默认是无限大（或者说是 Python 内部实现的一个较大的值），只要内存允许，所有的结果都会被缓存。
3. 在代码中的具体作用：
在动态规划问题中，比如这个硬币找零问题，每个子问题（即不同的剩余金额 rem）可能会被多次计算。如果不使用缓存，每次都要重新计算，会导致大量重复计算，影响效率。而 @functools.lru_cache(amount) 可以确保每个子问题只计算一次，之后的调用直接从缓存中取值，大大提高了程序的运行速度。
4. 示例：
假设 amount = 5，则 lru_cache 最多会缓存5个不同rem值的结果。如果有更多的不同rem需要计算，最早缓存的结果会被移除，缓存最新的结果。
总结：
@functools.lru_cache(amount) 通过缓存函数的返回值，避免了对相同输入的重复计算，特别适合用于具有大量重复计算的递归问题。指定缓存的容量 amount 可以控制缓存的大小，避免内存的过度使用。
方法二、动态规划
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 初始化dp数组，长度为amount+1，初始值为正无穷大，表示所有金额都无法凑出
dp = [float('inf')] * (amount + 1)
# base case: 当金额为0时，不需要任何硬币，所以dp[0]设为0
dp[0] = 0
# 遍历每一个硬币
for coin in coins:
# 对于每一个硬币，更新dp数组
for x in range(coin, amount + 1):
# dp[x]表示金额x所需的最少硬币数
# 更新dp[x]为当前dp[x]和使用当前硬币后dp[x - coin] + 1的最小值
dp[x] = min(dp[x], dp[x - coin] + 1)
# 如果dp[amount]依然是正无穷大，表示无法凑出该金额，返回-1
# 否则返回dp[amount]，表示凑出该金额所需的最少硬币数
return dp[amount] if dp[amount] != float('inf') else -1
时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
空间复杂度：O(S)。数组 dp 需要开长度为总金额 S 的空间。
第三题、198.打家劫舍
方法、动态规划
首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k (k>2) 间房屋，有两个选项：
偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
dp[i]=max(dp[i−2]+nums[i],dp[i−1])
边界条件为：
dp[0]=nums[0] 只有一间房屋，则偷窃该房屋
dp[1]=max(nums[0],nums[1]) 只有两间房屋，选择其中金额较高的房屋进行偷窃
最终的答案即为 dp[n−1]，其中 n 是数组的长度。
class Solution:
def rob(self, nums: List[int]) -> int:
# 如果房屋列表为空，返回0，因为没有房子可以偷
if not nums:
return 0
size = len(nums)
# 如果只有一个房子，直接返回那个房子的金额
if size == 1:
return nums[0]
# 创建dp数组，用于存储到每个房子为止能偷到的最大金额
dp = [0] * size
# 初始化第一个房子的金额
dp[0] = nums[0]
# 初始化第二个房子的金额，取第一个和第二个房子中金额较大的那个
dp[1] = max(nums[0], nums[1])
# 从第三个房子开始计算
for i in range(2, size):
# dp[i]是偷到第i个房子的最大金额，取偷第i个房子和不偷第i个房子两种情况中的最大值
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
# 返回最后一个房子的最大金额
return dp[size - 1]
优化：上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。
class Solution:
def rob(self, nums: List[int]) -> int:
# 如果房屋列表为空，返回0，因为没有房子可以偷
if not nums:
return 0
size = len(nums)
# 如果只有一个房子，直接返回那个房子的金额
if size == 1:
return nums[0]
# 初始化两个变量，first 和 second
# first 表示偷到前一个房子时的最大金额
# second 表示偷到当前房子时的最大金额
first, second = nums[0], max(nums[0], nums[1])
# 从第三个房子开始计算
for i in range(2, size):
# 更新 first 和 second
# first 变成 second 的旧值，即之前的最大金额
# second 更新为在偷当前房子和不偷当前房子两种情况下的最大值
first, second = second, max(first + nums[i], second)
# 返回最后一个房子时的最大金额
return second
时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
空间复杂度：O(1)。使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)。
第四题、213.打家劫舍2
和第 198 题的不同之处是，这道题中的房屋是首尾相连的，第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。
方法、动态规划
首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
注意到当房屋数量不超过两间时，最多只能偷窃一间房屋，因此不需要考虑首尾相连的问题。如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。
如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。
假设数组 nums 的长度为 n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1]。在确定偷窃房屋的下标范围之后，即可用第 198 题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。
假设偷窃房屋的下标范围是 [start,end]，用 dp[i] 表示在下标范围 [start,i] 内可以偷窃到的最高总金额，那么就有如下的状态转移方程：
dp[i]=max(dp[i−2]+nums[i],dp[i−1])
边界条件为：
dp[start]=nums[start] 只有一间房屋，则偷窃该房屋
dp[start+1]=max(nums[start],nums[start+1]) 只有两间房屋，偷窃其中金额较高的房屋
计算得到 dp[end] 即为下标范围 [start,end] 内可以偷窃到的最高总金额。
分别取 (start,end)=(0,n−2) 和 (start,end)=(1,n−1) 进行计算，取两个 dp[end] 中的最大值，即可得到最终结果。
根据上述思路，可以得到时间复杂度 O(n) 和空间复杂度 O(n) 的实现。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额，将空间复杂度降到 O(1)。
class Solution:
def rob(self, nums: List[int]) -> int:
# 定义一个辅助函数，用于计算在指定范围内的最大偷窃金额
def robRange(start: int, end: int) -> int:
# 初始化两个变量，表示在偷到当前房子时的最大金额
first = nums[start]
second = max(nums[start], nums[start + 1])
# 从第三个房子开始计算
for i in range(start + 2, end + 1):
# 更新first和second
# first变成second的旧值，即之前的最大金额
# second更新为在偷当前房子和不偷当前房子两种情况下的最大值
first, second = second, max(first + nums[i], second)
# 返回在当前范围内的最大偷窃金额
return second
# 获取房子的数量
length = len(nums)
# 特殊情况处理
if length == 1:
return nums[0] # 如果只有一个房子，返回那个房子的金额
elif length == 2:
return max(nums[0], nums[1]) # 如果有两个房子，返回两个房子中金额较大的一个
else:
# 计算两种情况的最大值：
# 1. 不偷第一个房子，只考虑从第二个到最后一个房子的情况
# 2. 不偷最后一个房子，只考虑从第一个到倒数第二个房子的情况
# 返回两种情况中的最大值
return max(robRange(0, length - 2), robRange(1, length - 1))
时间复杂度：O(n)，其中 n 是数组长度。需要对数组遍历两次，计算可以偷窃到的最高总金额。
空间复杂度：O(1)。
第五题、121.买卖股票的最佳时机
需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。
形式上，对于每组 i 和 j（其中 j>i）需要找出 max(prices[j]−prices[i])。
方法一、暴力（超时）
# 此方法会超时
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
ans = max(ans, prices[j] - prices[i])
return ans
方法二、一次遍历
假设给定的数组为：[7, 1, 5, 3, 6, 4]
如果在图表上绘制给定数组中的数字，将会得到：
用一个变量记录一个历史最低价格 minprice，在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此，只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果是在历史最低点买进的，那么今天卖出能赚多少钱？当考虑完所有天数之时，就得到了最好的答案。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 初始化最小价格为一个非常大的值
inf = int(1e9)
minprice = inf
# 初始化最大利润为0
maxprofit = 0
# 遍历每一个价格
for price in prices:
# 更新最大利润，取当前价格减去最小价格和当前最大利润的最大值
maxprofit = max(price - minprice, maxprofit)
# 更新最小价格，取当前价格和已知最小价格的最小值
minprice = min(price, minprice)
# 返回最终的最大利润
return maxprofit
时间复杂度：O(n)，只需要遍历一次。
空间复杂度：O(1)，只使用了常数个变量。
- 买卖股票的最佳时机2 前天刷过 方法一、动态规划 方法二、贪心
