C++动态规划经典试题解析之打家劫舍系列

1.前言

力扣上有几道与打家劫舍相关的题目，算是学习动态规划时常被提及的经典试题，很有代表性，常在因内大大小小的社区内看到众人对此类问题的讨论。

学习最好的方式便是归纳总结、借鉴消化，基于这个目的，本文对此类问题也做了讲解，在一些优秀思想的基础上添加了个人观点。

闲话少说，进入正文，开始打家劫舍，看今晚收获几何？

2. 线性盗贼

2.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。

2.2 问题分析

在打劫之前先不要急入进入房间，应该是先做全局的估算。

想象当盗贼从第一间房屋开始偷窃，他可以选择是偷还是不偷。偷还是不偷的选择不是源于他瞬时良心上的发现，而是收益的多少。如果只有一间房间，他会毫不犹豫的选择偷，这样才能带来今晚最大的收益。

下图所示为当只有一间房子时盗贼能获取到的最高金额。

如果有 2 间房屋，盗贼面对第一间房屋时会如何想呢？

收益固然重要，但是如果触发了报警系统，偷鸡不成蚀把米这样的赔本生意，肯定是不能做的。所以他的想法是可以偷，如果从此房间内的获取到的收益大于从另一个房间内获取到受益，否则，放弃当前房间，而选择进入第二间房间。

怎么知道偷还是不偷哪一个获取的收益最大。唯一法则就是比较，也就偷和不偷两者的受益取其大。如果只