题目:你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例1:输入:[1,2,3,1] 输出:4。
示例2:输入:[2,7,9,3,1] 输出:12。
题目链接:https://leetcode-cn.com/problems/house-robber/
思路分析:
解决这道题可以采用动态规划解决,可以借助斐波那切数列的思想来实现。
首先用Hn表示第n间房子的金额,f(n)表示能在前n家房子偷得的最大金额。
f(1)=H1 f(2)=max(H1,H2)
f(3)可以分成两种情况,H3抢或不抢,抢:f(3)=H1+H3=f(1)+H3,不抢:f(3)=max(H1,H2) =f(2)。
同理f(4)也可以分为两种情况,H4抢或不抢,抢:f(4)=f(2)+H4,不抢:f(4)=f(3)。
而决定抢不抢在于哪种金额更大。
因此我们可以得到一个公式f(n)=max(f(n-2)+Hn,f(n-1))。
代码实现:
图1.代码实现
测试案例[2,7,9,3,1],变量值变化过程,最后输出12:
图2.变量值变化