数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 实现打家劫舍 II
假设你是一名职业劫匪，你计划沿街抢劫房屋。每栋房子都储存着一定数量的钱。所有房屋都排成一个圆圈。这意味着第一栋房子是最后一栋房子的邻居。我们必须记住，相邻的房屋连接着安全系统，如果在同一个晚上闯入两栋相邻的房屋，它会自动报警。因此，如果我们有一个整数列表，表示每栋房子的金额，请确定你可以在一个晚上抢劫的最大金额，而不会触发警报。例如，如果数组是 [1,2,3,1]，则输出将是 4。
为了解决这个问题，我们将遵循以下步骤：
- 我们使用一个名为 solve() 的模块，它将接收数组、起始位置和结束位置作为参数，其作用如下：
- ans := nums[start]
- 创建一个用于动态规划的表格，命名为 dp，大小与 nums 相同。
- dp[start] := nums[start]
- for i := start + 1 to end
- last := dp[i – 1]
- lastToLast := 如果 i – 2 存在，则为 dp[i – 2]，否则为 0
- dp[i] := nums[i] + lastToLast 和 last 的最大值
- ans := dp[i] 和 ans 的最大值
- return ans
- 抢劫过程如下：
- n := nums 的大小
- 如果 n 为零，则返回 0
- 如果 n = 1，则返回 nums[0]
- 返回 solve(nums, 0, n - 2) 和 solve(nums, 1, n – 1) 的最大值
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int>& nums, int start, int end){
int ans = nums[start];
vector <int> dp(nums.size());
dp[start] = nums[start];
for(int i = start + 1; i <= end; i++){
int last = dp[i - 1];
int lastToLast = i - 2 < start? 0 : dp[i - 2];
dp[i] = max(nums[i] + lastToLast, last);
ans = max(dp[i], ans);
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(!n)return 0;
if(n == 1)return nums[0];
return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
};
main(){
vector<int> v = {1,2,3,5};
Solution ob;
cout << ob.rob(v);
}输入
[1,2,3,5]
输出
7
更新于: 2020年5月4日
712 次浏览
广告