打家劫舍
题目 打家劫舍
题目描述 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
样例
思路分析
不能简单的分析成 间隔一个偷——只偷奇数或者只偷偶数
这个问题其实还可以偷1 然后23不偷 再偷4 即可以不止间隔一个
所以想着分奇偶排序取两端求平均比大小是不可行的
可以发现 对于每个房间 不外乎就是两种选择 偷与不偷
若偷1的话 下一个一定是先从3开始考虑 如果不偷1的话 下一个一定是先从2开始考虑
（往左表示不偷该点 往右表示偷该点）
可以发现如果往右走 就需要加上前者累积的金额
还是可以先用暴搜实现 每一个房间 不偷的话递归处理它的下一个房间 偷的话递归处理它的下下个房间 且加上当前房间的金额数
然后就是用记忆化数组 省去一些不必要的分支
再然后舍去递的过程 直接做归（也就是推） 即简单dp
如图也可见 大的是在递归搜索树的树叶处
所以应该是从大到小递推 推到1的时候停止得出答案
代码实现
暴搜
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int home[N];
int n,T;
int dfs(int x)
{
if(x>n)
return 0;
//不同处在于这里返回的是max而不是和
else
//如果该点不偷就往左走找临近的店 如果偷就往隔两个的店考虑 并加上当前累计值
return max(dfs(x+1),dfs(x+2)+home[x]);
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>home[i];
int res=dfs(1);//从第一个店看 偷不偷
cout<<res<<endl;
}
return 0;
}
记忆化数组
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int home[N];
int mem[N];//添加记忆化数组
int n,T;
int dfs(int x)
{
if (mem[x])
return mem[x];
int sum=0;
if(x>n)
sum=0;
else
sum= max(dfs(x+1),dfs(x+2)+home[x]);
mem[x]=sum;
return sum;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>home[i];
memset(mem,0,sizeof mem);//记得这里重置记忆化数组
int res=dfs(1);
cout<<res;
}
return 0;
}
dp
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int home[N];
int f[N];
int n,T;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>home[i];
memset(f,0,sizeof f);
//因为1是由2 3的状态（小的根据大的）得出的 所以n应该由大到小
for(int i=n;i>=1;i--)
{
f[i]=max(f[i+1],f[i+2]+home[i]);
}
cout<<f[1];
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf=0x3f3f3f3f;
const int N=100010;
int home[N];
int dp[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// 偷第i家 状态从第i-2转移来 不偷第i家 状态由第i-1转移来
// 只有一家的最优解是偷这家 有两家的最优解是选价值最高的一家偷
int T;cin>>T;
while(T--){
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>home[i];
dp[1]=home[1];dp[2]=max(home[1],home[2]);
for(int i=3;i<=n;i++){
dp[i]=max(dp[i-1],dp[i-2]+home[i]);
}
cout<<dp[n]<<endl;
}
return 0;
}
💬 评论