272最大化糖果美味值问题

题解

题目要求在一个长度为 n 的数组中，选择一些糖果作为奖励，满足以下限制规则：

• 如果选择了编号为 i 的糖果，那么编号为 i-1、i-2、i+1、i+2 的糖果将不能被选择。
• 每个糖果都有一个对应的美味值。
• 目标是使所选糖果的美味值之和最大。

解题思路

1. 动态规划：

   定义 f[i] 为考虑前 i 个糖果时，满足条件的最大美味值之和。

2. 状态转移：

   对于每个糖果 i，有两种选择：

   • 不选择：则 f[i] = max(f[i-1], f[i-2])
   • 选择：则不能选择 i-1、i-2，因此 f[i] = f[i-3] + a[i]

   综合考虑，状态转移方程为：

   f[i] = max(f[i-1], f[i-2], f[i-3] + a[i])

3. 空间优化：

   由于每次只需要记录前三个状态，可以使用三个变量 f1, f2, f3 来代替数组 f，从而降低空间复杂度。

4. 返回结果：

   最终返回 f1，即考虑所有糖果后的最大美味值之和。

代码

def solution(n: int, a: list) -> int:
    f1 = f2 = f3 = 0
    for i in range(n):
        # f[i] = max(f[i - 1], f[i - 2], f[i - 3] + a[i])
        f1, f2, f3 = max(f1, f2, f3 + a[i]), f1, f2
    return f1

if __name__ == '__main__':
    print(solution(7, [3, 1, 2, 7, 10, 2, 4]) == 14)
    print(solution(5, [1, 10, 2, 5, 8]) == 18)
    print(solution(6, [4, 5, 6, 1, 2, 3]) == 9)

复杂度分析

• 时间复杂度：O(n)，其中 n 是糖果的数量。需要遍历一次数组。
• 空间复杂度：O(1)，仅使用常数级别的额外空间。