🏠LeetCode——198.打家劫舍分治解法（独家）
type
status
date
slug
summary
tags
category
icon
password
目前几乎所有解法都是采用动态规划，但是采用分治可以巧妙解决该问题，该解法的代码量小，并可获得最优的时间和空间复杂度。
Problem: 198.打家劫舍
思路
想象，小偷同志每次经过一栋房屋都面临两个选择，偷or不偷，那我们就从最后一栋房子开始，分这两种情况开始考虑。
解题方法
如果偷完最后一栋房屋的最大收益是，没偷最后一栋房屋的最大收益是，那么总得最大收益就是。那么我们可以得出：
其中，是房屋收益列表。
第1个公式：偷当前房屋，最大收益为：不偷上一个房屋的最大收益 + 当前房屋的收益；
第2个公式：不偷当前房屋，最大收益为：偷上一个房屋的最大收益 不偷上一个房屋的最大收益，二者的最大值。
如果有疑问，欢迎交流。
复杂度
时间复杂度:Q(n)
空间复杂度:Q(1)