算法题每日一练---第37天：打家劫舍

一、问题描述

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

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

题目链接：打家劫舍

二、题目要求

样例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 。

数据范围

• 1 <= nums.length <= 100`
• 0 <= nums[i] <= 400`

考察

1.动态规划中等题型

2.建议用时5~15min

三、问题分析

这也是一道比较典型的动态规划问题，动态规划没做过的可以看这一篇入门题解：

算法题每日一练---第34天： 青蛙跳台阶

还是用我们的三步走，老套路：

第一步含义搞懂：

首先，使用动态规划一维数组就可以解决问题，那么这个dp[i]到底代表什么？

看看题目问什么，在不触犯警报的情况下，偷到的最大金额数，那么dp[i]就代表从截止到第i个房子，最大的金额数。

第二步变量初始：

假如房子数目为1,那么dp[0]=nums[0]

假如房子数目为2,那么dp[1]=max(nums[0],nums[1])

第三步规律归纳：

那么到底有什么规律呢？我把样例2详细列出来你看一下：

从第三个数开始，dp[i]是不是满足

dp[i]=max(dp[i−2]+nums[i],dp[i−1])关系式

三步走，打完收工！

四、编码实现

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

	int n,nums[105],i,dp[105];//初始化

	cin>>n;//输入数组的大小,n为0或1力扣要判断的，我这里省去了

	for(i=1;i<=n;i++)//输入数组的元素

		cin>>nums[i];

	dp[1]=nums[1],dp[2]=max(nums[1],nums[2]);//初始化动态规划前两位

	for(i=3;i<=n;i++)//第三位开始循环

	{

		dp[i]=max(dp[i-1],nums[i]+dp[i-2]);//找到规律

	}

	cout<<dp[n];//输出结果

	return 0;

}

五、测试结果