# 第69期-基础算法：动态规划 打家劫舍
Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。
# 1 问题描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
示例 3:
输入: [2,1,1,2]
输出: 4
初始代码
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
#在此之间填写代码
print(Solution().rob([1,2,3,1]))
print(Solution().rob([2,7,9,3,1]))
print(Solution().rob([2,1,1,2]))
2
3
4
5
6
7
8
# 2 解题思路
- 标签：动态规划
- 首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。
- 如果只有两间房屋，则由于两间房屋相邻，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
- 如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第k(k>2)间房屋，有两个选项：
- 1、偷窃第k间房屋，那么就不能偷窃第k−1间房屋，偷窃总金额为前k−2间房屋的最高总金额与第k间房屋的金额之和。
- 2、不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
- 根据以上思路获取解题方法
# 3 解题方法
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
a=len(nums)
i=2
if a==1:return nums[0]
nums[1]=max(nums[0],nums[1])
while i<a:
nums[i]=max(nums[i-1],nums[i-2]+nums[i])
i+=1
return max(nums[-1],nums[-2])
print(Solution().rob([1,2,3,1]))
print(Solution().rob([2,7,9,3,1]))
print(Solution().rob([2,1,1,2]))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
第1-3，13-15行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义变量a并赋值列表的长度，也就是房屋的个数
第5行： 定义i=2，因为当只有一个房间的时候需要另外考虑
第6行： 当只有一个房屋时，返回该房屋对应的值
第7行： 当房屋大于等于2时，将前两个房间中的最大值赋值给2，避免出现错误
第8行： 开始循环，当i<a的时候，执行循环，知道遍历完所有房屋为止
第9行： 计算到当前房屋可以获得的最大值并赋值给当前房屋，比较的值分别是到前一个房屋的最大值以及到前两个房屋后到此房屋的最大值。
第10行： 索引加一进行下个房屋计算
第11行： 所有房屋计算完毕后，返回到最后两个房屋时可以获得的最大值
代码运行结果为：
# 算法讲解
这里用到了基础算法：动态规划，简单讲解下这个算法：
动态规划
动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
性质
1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
3. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
性质
1. 划分：按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的
2. 确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性
3. 确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程
4. 边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件
# 4 视频解析
高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码 