198. House Robber
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.
题解：
n 个房屋，每个房屋对应着不同的财宝，从相邻的两个房屋中盗取财宝就触发报警器，求在不触发报警器的情况下，最多可以盗取多少财宝；
输入6个房屋的财宝：nums = [5, 2, 6, 3, 1, 7]；
最大财宝（最优解）：5 + 6 + 7 = 18；
原问题：n个房屋的最优解
子问题：
前1个房屋的最优解：dp[0] = nums[0]；
前2个房屋的最优解：dp[1] = max(dp[0], nums[1])；
前3个房屋的最优解：包含第三个房间：dp[0] + nums[2]；不包含第三个房间：dp[1]；则 dp[2] = max(dp[1], dp[0] + nums[2])；
确认状态：
n个房屋的最优解(dp[n-1])：包含第n个房间：dp[n-3] + nums[n-1]；不包含第n个房间：dp[n-2]；
得到动态规划转移方程：dp[n-1] = max(dp[n-2], dp[n-3] + nums[n-1])；
边界状态：dp[0] = nums[0]；dp[1] = max(dp[0], nums[1])；
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int rob(vector<int> &nums) {
if (nums.size() == 0) {
return 0;
}
if (nums.size() == 1) {
return nums[0];
}
vector<int> dp(nums.size() + 3, 0);
dp[0] = nums[0];
dp[1] = max(dp[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
int main() {
vector<int> nums;
nums.push_back(5);
nums.push_back(2);
nums.push_back(6);
nums.push_back(3);
nums.push_back(1);
nums.push_back(7);
Solution s;
printf("最大财宝：%d", s.rob(nums));
return 0;
}
结果
最大财宝：18
My Solution:
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = []
if len(nums) == 0:
return 0
dp.append(nums[0])
if len(nums) > 1:
dp.append(max(nums[0], nums[1]))
for i in range(2, len(nums)):
dp.append(max(dp[i-1], dp[i-2] + nums[i]))
return dp[len(nums)-1]
