题目描述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
解题思路
- 题目描述，找一个数组的不连续的最大和（不能是挨边的元素）
- 考察动态规划，转移方程的推导
- 用一个一维数组dp[i]代表[0,i]之间元素的最大值
- 动态规划来说，对于当前元素i来说，有抢还不抢两种选择，不抢即代表是当前元素的上一个元素dp[i-1]
- 抢代表着dp[i - 2] + nums[i]
- 抢与不抢，选择一个最大值。
- 即max(dp[i - 2] + nums[i], dp[i - 1])
-
举个例子， nums为{3, 2, 1, 5}，那么来看 dp 数组应该是什么样的，首先 dp[0]=3 没啥疑问，再看 dp[1] 是多少呢，由于3比2大，所以抢第一个房子的3，当前房子的2不抢，则dp[1]=3，那么再来看 dp[2]，由于不能抢相邻的，所以可以用再前面的一个的 dp 值加上当前的房间值，和当前房间的前面一个 dp 值比较，取较大值当做当前 dp 值，这样就可以得到状态转移方程 dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 且需要初始化 dp[0] 和 dp[1]，其中 dp[0] 即为 num[0]，dp[1] 此时应该为 max(num[0], num[1])，
C++代码
class Solution {
public:
int rob(vector<int>& nums) {
int res = 0;
if(nums.size() == 0){
return 0;
}
if(nums.size() == 1){
return nums[0];
}
int dp[nums.size()];
memset(dp, 0, sizeof(int) * nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
解题思路
- 动态规划
- 初始化阶段，首先dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
- 对于i(i>=2)来说，有两种选择,即dp[i] 是 dp[i - 2] + nums[i], 还是 dp[i - 1]
- 找到一个最大的即可
C++代码
class Solution {
public:
int rob(vector<int>& nums) {
int res = 0;
if(nums.size() == 0){
return 0;
}
if(nums.size() == 1){
return nums[0];
}
if(nums.size() == 2){
return max(nums[0], nums[1]);
}
int dp[nums.size()] = {0};
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
if(dp[i] > res){
res = dp[i];
}
}
return res;
}
};
