【蓝桥杯算法 | 状态机DP模型】

def maxEnergy(energyDrinkA, energyDrinkB):
    N = len(energyDrinkA)
    dp = [[0] * 2 for _ in range(N)] # 存储第i时刻喝A或者B饮料两种状态的最大值
    dp[0][0] = energyDrinkA[0]
    dp[0][1] = energyDrinkB[0]
    
    for i in range(1, n):
        # 第i时刻饮用 A
        dp[i][0] = max(dp[i - 1][0] + energyDrinkA[i],  # 继续喝 A
                       dp[i - 1][1])                  # 切换到 A，这一小时内不摄入内量
        
        # 第i时刻饮用 B
        dp[i][1] = max(dp[i - 1][1] + energyDrinkB[i],  # 继续喝 B
                       dp[i - 1][0])                  # 切换到 B，上一小时喝 A
    return max(dp[n - 1][0], dp[n - 1][1])

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 第一个数组存储第i次没偷， 第二个数组存储第i次偷了
        dp = [[0 for _ in range(len(nums))] for _ in range(2)] 
        dp[1][0] = nums[0] 
        for i in range(1, len(nums)):
            dp[0][i] = max(dp[0][i-1], dp[1][i-1])
            dp[1][i] = dp[0][i-1] + nums[i] #第i家偷了，上一家指定没偷
        return max(max(dp[0]), max(dp[1]))

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        n = len(nums)
        dp = [[0] * n for _ in range(4)]
        dp[1][0] = nums[0]
        for i in range(1, n):
            if i < n - 1: 
                dp[0][i] = max(dp[0][i-1], dp[1][i-1]) 
                dp[1][i] = dp[0][i-1] + nums[i]
                dp[2][i] = max(dp[2][i-1], dp[3][i-1])
                dp[3][i] = dp[2][i-1] + nums[i]
            else:  
                dp[0][i] = max(dp[0][i-1], dp[1][i-1])
                dp[1][i] = dp[0][i-1] # 最后一家不偷，不需要加上nums[i]
                dp[2][i] = max(dp[2][i-1], dp[3][i-1])
                dp[3][i] = dp[2][i-1] + nums[i]  

        return max(dp[0][n-1], dp[1][n-1], dp[2][n-1], dp[3][n-1])

class Solution:
    def __init__(self):
        self.min_capacity = float('inf')  # 记录最小窃取能力

    def backtrack(self, nums, k, start, current_count, max_amount):
        # 如果已经窃取了至少 k 间房屋，更新最小窃取能力
        if current_count >= k:
            self.min_capacity = min(self.min_capacity, max_amount)
            return
        
        for i in range(start, len(nums)):
            # 选择当前房屋，更新最大金额，并跳过相邻房屋递归
            self.backtrack(nums, k, i + 2, current_count + 1, max(max_amount, nums[i]))

    def minCapability(self, nums: List[int], k: int) -> int:
        # 从第0个房屋开始回溯
        self.backtrack(nums, k, 0, 0, 0)
        return self.min_capacity