【LeetCode】198. House Robber

LeetCode-198

Links:https://leetcode.com/problems/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个篮子排成一行，每个篮子内有若干鲜花，现在你可以拿走其中一部分，拿取规则是不能拿相邻篮子…比如拿走 3 号则不能拿2和4…（题目翻译不是这个意思，但是为了和谐…对不对）问能拿到的最大鲜花数量…

解法：DP即可.DP公式：D[i] = Max(D[i-2]+A[i],D[i-1]);

这里A[i]的值是第一个篮子内花的数量，D[i]的值是前i个篮子选取的情况下，最大获得鲜花数量.

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums.size()>1)nums[1] = max(nums[1],nums[0]);
        for(int i=2;i<nums.size();i++)
        {
            nums[i] = max(nums[i-2]+nums[i],nums[i-1]);
        }
        return nums[nums.size()-1];
    }
};

class Solution {

public:

int rob(vector<int>& nums) {

if(nums.size()==0)return 0;

if(nums.size()>1)nums[1] = max(nums[1],nums[0]);

for(int i=2;i<nums.size();i++)

{

nums[i] = max(nums[i-2]+nums[i],nums[i-1]);

}

return nums[nums.size()-1];

}

};

很简单的DP…

【LeetCode】198. House Robber

Tagged on: LeetCode