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

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

动态规划一直是算法中的一个难点，今天开始的一段时间内本长老会陆续更新一些动态规划的专题，由简单到困难，跟着长老一起学习动态规划吧！

今天先来一道题目热热身。

由题目可知，我们需要在给定的数组中寻找若干个数，使得这些数的总和最大，但是要求不能选择相邻的数。

遍历一遍所有的情况，那么长度为 $n$ 的数组就会有 $2^n$ 种可能的选择，求出所有选择中最大的和，这会非常浪费时间。

定义 dp[i] 表示到第 i 个房间为止，小偷能偷到的最大金额。