文章目录

• 打家劫舍问题（力扣198）
• • 问题描述
• 代码实现
• • 1、递归
  • 2、动态规划（自底向上）
  • 3、算法优化---空间压缩技术
  • 4、返回偷盗的房间编号

打家劫舍问题（力扣198）

问题描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

代码实现

1、递归

def steal_recursion(s):   # s --> 数组类型
    k = len(s)
    if k == 1:
        return s[0]
    if k == 2:
        return max(s)
    if k > 2:
        s1 = s[0:k-1]
        s2 = s[0:k-2]
        return max((s[-1] + steal_recursion(s2), steal_recursion(s1)))

时间复杂度：2的n次幂
存在大量重复操作

2、动态规划（自底向上）

def steal_from_bottom(s):
    k = len(s)
    if k == 1:
        return s[0]
    if k == 2:
        return max(s)
    dp = [0]*k
    dp[0], dp[1] = s[0], max(s[0:2])  # k>=3
    for i in range(2,k):
        dp[i] = max((dp[i-1],dp[i-2]+s[i]))   # 取数组中的元素，不用再调用原函数了
    return dp[k-1]

一开始写的时候，有个问题

def steal_from_bottom(s):
    k = len(s)
    dp = [0]*k
    if k == 1:
    	# 错误写法
    	dp[0] = s[0]    
        return s[0]     
    if k == 2:
        dp[1] = max(s)    # 错误
        return dp[1]
    dp[0], dp[1] = s[0], max(s[0:2])  # k>=3
    for i in range(2,k):
        dp[i] = max((dp[i-1],dp[i-2]+s[i])) 
    return dp[k-1]

在 k=0和k=1时，就试图修改列表中的元素，进行存储。
事实上，刚开始k并不等于1或2，那么这段代码跳过。
后面的：

dp[i] = max((dp[i-1],dp[i-2]+s[i])) 

也会因为前面未修改dp的第1、2个值而出错。

正确的做法是：
k=1或2时，直接返回。什么都不用管。
k>=3时，此时才生成DP数组，然后紧接着初始化前面的边界值（dp[0]、dp[1]），再来计算后面的数

3、算法优化—空间压缩技术

事实上，我们在每一次遍历到下一个房间偷盗总金额最大时，只需要知道前面两个房间的即可。并不需要一整个数组来存储前面全部的总金额。

因此，可以考虑设定两个变量，记录dp数组的前两个数值即可。随着房间数量的增加，不断更新这两个变量的值，直到最后一个房间。

def steal_compress(s):   # s--> 数组类型
    k = len(s)
    if k == 1:
        return s[0]
    if k == 2:
        return max(s)
    if k >= 3:
        pre1,pre2 = s[0],max(s[:2])
        for i in range(2,k):     # 每次遍历，都只需要存储前面两个的值，用两个指针pre1,pre2的移动表示
            result = max((s[k-1] + pre1, pre2))
            pre1 = pre2
            pre2 = result
        return result

4、返回偷盗的房间编号

def steal_get_index(s):
    k = len(s)
    if k == 1:
        return s[0]
    if k == 2:
        return max(s)
    # k >= 3
    dp = [0] * k
    dp[0], dp[1] = s[0], max(s[:2])
    for i in range(2,k):     # 存储 1~i 间的最大金额
        dp[i] = max((dp[i-2] + s[i], dp[i-1]))
        
    max_value = dp[-1]   # 初始化最大值，为偷盗最后一间房间。
    # list_index = []   # 存储的是 偷到最大金额的房间编号      -->  用字符串也可以存储，倒序输出，省时间空间
    str_index = ''   # 存储编号
    while True:
        index = dp.index(max_value)   # 寻找dp中第一次出现最大值的位置
        str_index += str(index) + ' '
         # dp中第一次出现最大值的位置，对应编号房间一定被偷  （dp中元素变大的位置，该位置房间一定被偷）
        current = s[index]     # 指针，表遍历到的当前位置的房间金额
        if max_value == current:   # 如果当前房间金额 = 更新后的最大值，即所有编号被找到
            return str_index[::-1]
        max_value = max_value - current   # max_value > current

1、在从后往前逐步获取被偷盗的房间时，已确认被偷的房间可以用列表存储后倒序输出。也可以直接采用字符串的拼接计数。
显然，用字符串存储编号，更加节省空间

2、在DP数组中，从后往前逐步获取第一次出现最大元素的位置。
！！！dp数组中元素变大的地方，对应的索引编号房间一定被盗。所以可以共用同一索引

3、while循环终止条件：前面所有房间最大总金额刚好等于该目前房间的金额