House Robber
思路:DP
- 状态表示:
- f[i]表示前i个数中选,不选nums[i]的选法的最大值
- g[i]表示前i个数中选,选择nums[i]的选法的最大值
- 参考:yxc
/*
* @lc app=leetcode id=198 lang=cpp
*
* [198] House Robber
*
* https://leetcode.com/problems/house-robber/description/
*
* algorithms
* Easy (41.22%)
* Likes: 2953
* Dislikes: 93
* Total Accepted: 361.6K
* Total Submissions: 876K
* Testcase Example: '[1,2,3,1]'
*
* 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.
*
* Example 1:
*
*
* Input: [1,2,3,1]
* Output: 4
* Explanation: Rob house 1 (money = 1) and then rob house 3 (money =
* 3).
* Total amount you can rob = 1 + 3 = 4.
*
* Example 2:
*
*
* Input: [2,7,9,3,1]
* Output: 12
* Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house
* 5 (money = 1).
* Total amount you can rob = 2 + 9 + 1 = 12.
*
*
*/
错误思路:以为求奇数和与偶数和就和可以,没想到[1,-2,3,12,5]这种情况的结果是13
/*
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
//vector<int> f(n);
int sum1 = 0, sum2 = 0;
int res;
if (n == 0) res = 0;
if (nums[n - 1] % 2 != 0)
for (int i = 0; i < n; i += 2)
sum1 += nums[i];
if (nums[n - 1] % 2 == 0)
for (int i = 1; i < n; i += 2)
sum2 += nums[i];
res = max(sum1, sum2);
return res;
}
};
*/
代码
class Solution{
public:
int rob(vector<int>& nums)
{
//f[i]表示前i个数中选,不选nums[i]的选法的最大值
//g[i]表示前i个数中选,选择nums[i]的选法的最大值
int n = nums.size();
vector<int> f(n + 1), g(n + 1); //数组中的每个元素开始都为0,相当于初始化
//一般情况下,当考虑选前i个数的时候,开n + 1
for (int i = 1; i <= n; i ++ )
{
//f[i] 应该等于max(前i-1中不选nums[i - 1]的最大值,和前i-1中选择num[i - 1]的最大值)
f[i] = max(f[i - 1], g[i - 1]);
//两个连续的数不能同时选,所以必然不能选到i-1
g[i] = f[i - 1] + nums[i - 1]; //注意:nums数组是从0开始, 所以这里是 i - 1
}
int res = max(f[n], g[n]);
return res;
}
};
// testcase [1,-2,3,12,5]
// result: 13
Python:
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
dp = [[0 for j in range(2)] for i in range(len(nums))]
dp[0][0] = 0
dp[0][1] = nums[0]
for i in range(1, len(nums)):
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]
return max(dp[len(nums)-1][0], dp[len(nums)-1][1])