Leetcode: House Robber

本文主要是介绍Leetcode: 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.

思路分析：
假设你是一名江洋大盗，沿街打劫。每间房屋中都有一定数目的钱财，但是你一个晚上不能同时打劫两个相邻的房间，因为会触发报警系统。问你一晚上能打劫到的最大金钱数目。
动态规划问题：
假设你打劫的i-1个房间的时候最大金额为dp[i-1]，则第i个房间的金额为max(dp[i-1], dp[i-2] + num[i-1])。即你要选择打劫第i-1个房间，或者不打劫i-1个房间，在打劫dp[i-2] + num[i-1]和不打劫dp[i-1]中选择最大的即是打劫到第i个房间的最大金额。

C++参考代码：

class Solution
{
public:int rob(vector<int> &num){size_t size = num.size();if (0 == size) return 0;vector<int> sum(size + 1, 0);//开辟size+1大小的空间，并赋值为0sum[1] = num[0];for (size_t i = 2; i < size + 1; ++i){sum[i] = max(sum[i - 1], sum[i - 2] + num[i - 1]);//动态规划递推公式}return sum[size];}
};

这篇关于Leetcode: House Robber的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---