HouseRobber II
2024-09-05 19:02:29
//
// Created by Administrator on 2021/7/27.
//
#ifndef C__TEST01_HOUSEROBBER2_HPP
#define C__TEST01_HOUSEROBBER2_HPP
#include <iostream>
#include <vector>
using namespace std;
class HouseRobber2 {
/* 有一 圈 N栋房子(0 - N-1),房子i里有A[i]个金币
* 一个窃贼想选择一些房子偷金币
* 但是不能偷任何挨着的两家邻居,否则会被警察逮住
* 最多偷多少金币
* 例子:
* 输入:A = {3, 8, 4}
* 输出:8(只偷第二家的金币)
* */
public:
HouseRobber2(vector<int> An);
int HouseRobber2DP(vector<int> &A);
private:
vector<int> A;
};
HouseRobber2::HouseRobber2(vector<int> An):
A(An){
A.resize(An.size());
}
int HouseRobber2::HouseRobber2DP(vector<int> &A) {
if(A.empty()) {
return 0;
}
int N = A.size();
//f[N]表示第N家时的最大偷的钱
vector<int> f1(N);
vector<int> f2(N);
f1[0] = 0;
f2[0] = 0;
for(int i = 1; i < N; ++i){
//没有偷最后一个房子
f1[i] = f1[i-1];
if(i > 1) {
f1[i] = max(f1[i - 2] + A[i - 1], f1[i - 1]);
}
//没有偷第一个房子
if(i == 1){
f2[1] = A[1];
continue;
}
f2[i] = f2[i-1];
if(i > 1) {
f2[i] = max(f2[i - 2] + A[i], f2[i - 1]);
}
}
return max(f1[N-1], f2[N-1]);
//return max(f1[N-1],f2[N-1]);
}
#endif //C__TEST01_HOUSEROBBER2_HPP
最新文章
- asp.net 手工调用 WS(Get)方法:
- [OC笔记]@property之个人理解,大神轻拍
- LintCode Balanced Binary Tree
- 剖析ECMALL的登录机制
- Android(java)学习笔记195:学生信息管理系统案例(SQLite + ListView)
- 自定义view(自定义view的时候,三个构造函数各自的作用)
- 【Howie玩docker】-Docker常用命令操作
- 一个轻client,多语言支持,去中心化,自己主动负载,可扩展的实时数据写服务的实现方案讨论
- 实现ie6下的居中
- 利用python深度学习算法来绘图
- python_如何快速安装第三方库?
- Wcf host
- python turtle 书写新年快乐
- 第33章 密码学(Cryptography),密钥(Keys)和HTTPS - Identity Server 4 中文文档(v1.0.0)
- Gym101237C The Palindrome Extraction Manacher、SAM、倍增
- json序列化以及反序列化存在多个对象时候的处理
- Yii restful api跨域
- Cow Contest---poj3660
- 强制另存文件和加扩展名的代码c#
- CentOS安装Zabbix Agent