打家劫舍

1、198. 打家劫舍 题目描述

方法一：递归

class Solution:
    def rob(self, nums: List[int]) -> int:
        return self.robT(nums, len(nums)-1)        
    def robT(self, nums: List[int], lastIndex: int) -> int:
        if lastIndex == -1:
            return 0
        if lastIndex == 0 :
            return nums[0]
    
        
        # 抢最后一间房子， k-1将跳过
        sum1 = self.robT(nums, lastIndex-2) + nums[lastIndex]
        # 不抢最后一间房子， 
        sum2 = self.robT(nums, lastIndex-1)
        
        return max(sum1, sum2)

方法二： 迭代 方法三：动态规划 思路

f(k) = 从前 k 个房屋中能抢劫到的最大数额，Ai​ = 第 i 个房屋的钱数。 n = 1， f(1) = A1 n = 2， f(2) = max(A1， A2) n = 3时

• 抢第三间： 最大值就是 f(1) + A3
• 不抢第三间： 最大值为 f(2)

所以 f(3) = max(f(1)+A3, f(2))

所以到第k间抢到的最大金额为： f(k) = max(f(k-2) + Ak, f(k-1))

我们选择 f(–1) = f(0) = 0 为初始情况，这将极大地简化代码。

class Solution:
    def rob(self, nums: List[int]) -> int:
        preMax = 0
        curMax = 0
        for x in nums:
            tmp = curMax
            curMax = max(preMax + x, curMax)
            preMax = tmp
        return curMax

2、213. 打家劫舍 II

数组是个环，也就是说偷第一家，最后一家就不能偷；偷最后一家，第一家就不能偷。 所以，我们问题分成求 nums[0:n - 1]或者 nums[1:n]

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 0:
            return 0
        # 所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的
        # 所以第一间和最后一间，不能同时被抢，
        # 所以该问题变量两个问题[0: n-1], 和[1: n]的最优解
        return max(self.robOne(nums[0: len(nums)-1]), self.robOne(nums[1: len(nums)]))
    
    def robOne(self, nums: List[int]) -> int:
        preMax = 0
        curMax = 0
        for x in nums:
            tmp = curMax
            curMax = max(preMax + x, curMax)
            preMax = tmp
        return curMax

3、746. 使用最小花费爬楼梯

• dp[i] = min(dp[i] + dp[i - 1], dp[i] + dp[i - 2])
• 对于爬到顶端，取决于最后两阶的消耗

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        preMin = cost[0]
        curMin = cost[1]
        
        for i in range(2, len(cost)+1):
            if i == len(cost):
                curMin = min(curMin, preMin)
            else:
                tmpMin = curMin
                # dp[i] = min(dp[i] + dp[i - 1], dp[i] + dp[i - 2])
                curMin = min(preMin + cost[i], curMin + cost[i])
                preMin = tmpMin  
        return curMin

3.1、优化： 不需要对顶端特殊照顾，只需要在最后返回最后两阶的最小消耗

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        preMin = cost[0]
        curMin = cost[1]
        for i in range(2, len(cost)):
            tmpMin = curMin
            # dp[i] = min(dp[i] + dp[i - 1], dp[i] + dp[i - 2])
            curMin = min(preMin + cost[i], curMin + cost[i])
            preMin = tmpMin  
        return min(preMin, curMin)

3.2、不使用外部空间，直接操作原数组

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            # dp[i] = min(dp[i] + dp[i - 1], dp[i] + dp[i - 2])
            cost[i] = min(cost[i-2] + cost[i], cost[i-1] + cost[i])
        return min(cost[-1], cost[-2])