202402012338
tags: #dp

class Solution:
	def rob(self, nums: List[int]) -> int:
		n = len(nums)
		if n == 1:
			return nums[0]
		@lru_cache
		def dp(i, end):
			if i >= end:
				return 0
			return max(dp(i + 1, end), dp(i + 2, end) + nums[i])
		return max(dp(1, n), dp(0, n - 1))

Reference

https://leetcode.com/problems/house-robber-ii/