【c++】打家劫舍（动态规划）

打家劫舍

题目难度：高阶

时间限制：1000ms

内存限制：256mb

题目描述

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

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

输入格式

第一行一个整数n，表示房屋的数量。

第二行n个整数，空格隔开，依次表示沿街n个房屋内的现金数量。

输出格式

一个整数，表示小偷能得到的最高金额。

样例数据

输入样例

4
1 2 3 1

输出样例

4

数据范围

对100%的数据，2<n≤10^5，每个房屋内金额不超过1000。

思路:

不要被这个高阶的难度吓到了，其实很简单

首先，我们知道这是动态规划，所以定义一个数组，long long dp[n+10];

dp[i]代表从第一家一直偷到第i家最多能投到多少钱（比如dp[5]表示从第一家到第五家最多偷几块钱）

好的，现在我们只要知道，dp[i]等于什么就好了（状态转移方程）

分析一下，假设我们知道了dp[1]到dp[4]的所有结果，现在我们要求dp[5]，应该怎么求呢？

因为我们不能偷相邻的房间，所以现在我们求dp[5]有两种选择：

1、dp[5]=dp[4]，这是什么意思呢？就是说，我们从第一间房子偷到第四间房子，已经偷了很多钱（比如已经偷了114514元钱），如果从第一间房子偷到第三间房子，再偷第五间房子，可能只能偷到1元，这种时候，最好的情况就是偷到第四间房子停下来，不偷第五间了，所以dp[5]只能等于偷到第四件的最大钱数

2、dp[5]=dp[3]+a[5]，这又是什么意思呢？就是从第一间房子偷到第三间房子，再偷第五间房子，这样偷到的钱可能会比偷到第四间房子偷的多，所以我们就会选择能偷更多的2号方案（就是从第一间房子偷到第三间房子，再偷第五间房子）

现在我们知道了，已经有两种选择，所以dp[i]=max(dp[i-2]+a[i],dp[i-1]);

现在，我们还需要解决一个问题：

如果dp[i]=max(dp[i-2]+a[i],dp[i-1]);那么当i=3或者4时，需要用到dp[1]或dp[2]，但求dp[1]要求出dp[1-2]=dp[-1],但我们不可能有dp[-1]这个数组，所以，dp[1]和dp[2]要我们提前求出来

dp[1]就等于第一间房子的钱数（从第一间房子偷到第一间房子，我们最多只能把第一间房子的钱全拿走）

dp[2]=max(a[1],a[2]);从第一间房子偷到第二间房子，我们只能偷一间房子，否则就会触发警报，只能偷第一间或第二间

那么，我们现在就能写出程序了

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n;
	cin>>n;
	long long a[n+10],dp[n+10];//a存每间房子的钱数 
	for(int i=1;i<=n;i++){
		cin>>a[i];//读入 
	}
	for(int i=1;i<=n;i++){
		if(i==1){//提前处理dp[1] 
			dp[i]=a[i];
		}else if(i==2){//提前处理dp[2] 
			dp[i]=max(a[i-1],a[i]);
		}else{//否则就是正常状态了，直接把状态转移方程抄进去 
			dp[i]=max(dp[i-2]+a[i],dp[i-1]);
		}
	}
	cout<<dp[n];//输出从第一间房子偷到第n间房子最多偷多少 
	return 0;
}