首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 198 House Robber

Leetcode 198 House Robber

作者头像
triplebee
发布2018-01-12 14:46:37
5560
发布2018-01-12 14:46:37
举报

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.

每个房子有一定的钱,相邻房子不能同时被抢,如何最大化收益。

简单DP,记录到每个位置时的最大收益,那么dp[i] = max(dp[i-1], dp[i-2] + nums[i]),即取抢和不抢的最大值。

因为只和前面两个状态有关,因此又可以对空间复杂度进行优化,用两个变量分别表示前一个位置和再前面一个位置的最大值。

class Solution {
public:
    int rob(vector<int>& nums) {
        int a = 0;
        int b = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i&1) 
                a = max(a + nums[i], b);
            else 
                b = max(a, b + nums[i]);
        }
        return max(a, b);
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-03-13 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档