LeetCode 不相邻最大和题解

LeetCode 不相邻最大和题解题目描述给定一个数组计算不相邻元素的最大和。示例输入nums [1, 2, 3, 1]输出4解题思路方法动态规划思路使用动态规划dp[i] 表示考虑前 i 个元素能获得的最大和。dp[i] max(dp[i-1], dp[i-2] nums[i])。复杂度分析时间复杂度O(n)。空间复杂度O(1)。代码实现def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] prev2 0 prev1 nums[0] for i in range(1, len(nums)): curr max(prev1, prev2 nums[i]) prev2 prev1 prev1 curr return prev1 # 测试 def test_rob(): nums [1, 2, 3, 1] print(rob(nums)) # 输出4 if __name__ __main__: test_rob()总结不相邻最大和是动态规划的典型应用通过维护前两个状态来计算最大和。