House Robber
My SubmissionsTotal Accepted: 45702 Total Submissions: 142460 Difficulty: EasyYou 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.
Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.
Subscribe to see which companies asked this question
Hide Tags Dynamic Programming Show Similar Problems動態規劃：
//理清思路：
//最值方案問題，考慮采用動態規劃
//令maxV[i][0]表示第i個房子是獲取的最大值
//無論什麼時候最後一個人要麼是偷要麼不偷
//如果最後一個是偷，顯然maxV[i] = maxV[i - 2]+nums[i];
//如果最後一個是不偷，maxV[i]=maxV[i-1];
class Solution {
public:
int rob(vector& nums) {
int n = nums.size();
if(n == 0)
{
return 0;
}else if(n == 1)
{
return nums[0];
}
else
{
vector maxV(n, 0);
maxV[0] = nums[0];
maxV[1] = max(nums[0], nums[1]);
for(int i = 2; i < n; i ++)
maxV[i] = max(maxV[i-2]+nums[i], maxV[i-1]);
return maxV[n-1];
}
}
};
或者想九度女生排座位那道題一樣：
class Solution {
public:
int rob(vector& nums) {
int dp[10000][2];
int sum = 0;
dp[0][0] = nums[0];//偷
dp[0][1] = 0;//不偷
int i = 1;
for (; i
