`
Cwind
  • 浏览: 267114 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
博客专栏
793bb7df-a2a9-312d-8cb8-b66c3af482d1
LeetCode题解
浏览量:54246
社区版块
存档分类
最新评论

LeetCode[动态规划] - #198 House Robber

阅读更多

原题链接:#198 House Robber

 

要求:

原题是要为某盗贼设计一个能使其利益最大化的方案(这个场景并不和谐,在保持题意的情况下重新描述一个场景)。假设某糖果工厂有若干糖果机,每台糖果机每天产出不同数量的糖果,每天取糖果时不能同时取相邻两台糖果机的糖果(别问为什么),问每天能取得的最大糖果数量是多少。

 

糖果机产生的糖果数量集合可以看成一个整型数组。

 

难度:简单

 

分析:

考虑使用动态规划来解决此问题。当糖果机只有1台时,取走这台产出的所有糖果;当糖果机有两台时,取走产出较多的糖果。当糖果机有三台时,有两种取法,取走第二台的产出的糖果,或取出第一台与第三台的所有糖果。假设第n台糖果机产出的糖果数量为S(n), 取到第n台为止时取到的最大糖果总数量为M(n),则有:

M(1) = S(1)

M(2) = Max(S(1), S(2))

M(3) = Max(M(1)+S(3), M(2))

...

M(n) = Max(M(n-2)+S(n), M(n-1))

即是说,当取到第n台时,有两种方案,要么n-1台不取,此时糖果数量为前n-2台所取数量加上第n台的产出数量;要么第n台本身不取,保留前n-1台所取的总数量。在这两种方案中选取所取总数量较大者即可。

 

解决方案:

Java - 296 ms

public int rob(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        int[] maxMoney = new int[nums.length+1];
        maxMoney[nums.length] = 0;
        maxMoney[nums.length-1] = nums[nums.length-1];
        for(int i=nums.length-2; i>=0; i--){
            maxMoney[i]=(nums[i]+maxMoney[i+2]>maxMoney[i+1])?(nums[i]+maxMoney[i+2]):maxMoney[i+1];
        }
        return maxMoney[0];
    }

 简单测试程序

    

 

2
3
分享到:
评论

相关推荐

    python-leetcode题解之198-House-Robber.py

    标题中提到的“python-leetcode题解之198-House-Robber.py”指的是一段用Python编写的针对LeetCode网站上编号为198的“打家劫舍”问题的解答代码。LeetCode是一个提供算法面试准备题库的平台,其中包含了大量的编程...

    c语言-leetcode题解之0337-house-robber-iii

    c c语言_leetcode题解之0337_house_robber_iii

    python-leetcode题解之213-House-Robber-II.py

    标题 "python-leetcode题解之213-House-Robber-II.py" 指明了文章的主体内容,即提供了一个Python语言编写的代码示例,用于解决LeetCode网站上的第213题——“打家劫舍 II”问题。这道题是“打家劫舍”系列问题的...

    最大公共字符串leetcode-HouseRobber-Problem-LeetCode-:HouseRobber-问题-LeetCode-

    HouseRobber-问题-LeetCode- @Faizansayeed28 代码 /** * 问题陈述- 你是一名职业劫匪,计划抢劫街道上的房屋。 每个房子都有一定数量的钱 藏起来,阻止你抢劫他们的唯一限制是相邻的房子有安全系统 连接,如果同一...

    leetcode和oj-OJ_Solution:leetcode、poj等OJ解决方案

    leetcode 和 oj OJ_Solution Solutions for OJ such as leetcode, poj and so on 版本 ...https://leetcode.com/problems/two-sum/ ...java/houserobber https://leetcode.com/problems/house-robber/

    LeetCode:Leetcode-解决方案

    House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. Maximum Length of Pair Chain [646]10. Integer Break [343]11. Count Numbers with Unique ...

    javascript-leetcode面试题解动态规划问题之第198题打家劫舍-题解.zip

    本题解将深入探讨第198题“打家劫舍”(House Robber),这是一个典型的动态规划问题,对于理解该算法模式及其应用至关重要。 动态规划是一种解决最优化问题的方法,通过将大问题分解为更小的子问题来求解。在这个...

    python-leetcode面试题解之第198题打家劫舍-题解.zip

    本压缩包中的内容是针对LeetCode平台上的第198题“打家劫舍”(House Robber)的Python解决方案。 “打家劫舍”是一道经典的动态规划问题,其核心在于寻找最优策略,即在不触动相邻房屋的情况下,最大化抢劫的财富...

    leetcode卡-leet-code-may-challenge:包含对MayChallenge(LeetCode)上发布的问题的解决方案。

    1. 动态规划:如“House Robber”问题,考察了如何用动态规划状态转移方程来求解最优决策。 2. 二叉树:例如“Lowest Common Ancestor of a Binary Tree”涉及到二叉树的遍历和节点查找。 3. 图论:如“Course ...

    leetcode分类-leetcode:leetcode刷题(中等难度分类)

    2. 动态规划:"House Robber"(打家劫舍)系列问题,展示了动态规划在求解最优解方面的应用,通过状态转移方程可以求得最大收益。 3. 分治法:"Median of Two Sorted Arrays"(两个排序数组的中位数)是分治策略的...

    leetcode最大蓄水量-leetcode:记录自己leetocde的过程

    学会了数组的创建,以及动态规划最基本的题目 2021.2.2 322 兑换钱币 学会了 Arrays.fill 的使用,以及查看源码,返回 记录在哔哩哔哩 中 2021.2.3 53 最大子数字之和 先更新max,再将负数赋值为0 62 不同的路径 arr...

    lrucacheleetcode-LeetCode:复制和思考

    lru cache leetcode LeetCode copy and think 加油学习 1. 时间轴 时间 题目 描述 知识点 ...198. House Robber 动态规划 如何确定子问题 20200525 20200525 20200525 20200525 20200525 20200525 $1 234

    LeetCode判断字符串是否循环-data-structure-and-algo:C++中的数据结构和算法

    HouseRobber(#198), ClimbingStairs(#70), CoinChange(#322), EditDistance(#72) 图 : 集合的合并(直接求并、按大小求并和按深度求并)、根搜寻(路径压缩) : 有向图和无向图的邻接表表示方法 : 图的深度优先和广度...

    lrucacheleetcode-LeetCode:CppSourceCode的LeetCode解决方案

    算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time to Buy and Sell Stock 122 买卖股票的最佳时机 Ⅱ Best Time to Buy and...

    python-leetcode面试题解之第337题打家劫舍III.zip

    在LeetCode平台上,第337题“打家劫舍III”(House Robber III)是一道涉及深度优先搜索(DFS)和树结构的经典算法题。这道题目要求我们通过Python编程来解决一个树形结构下的抢劫问题,旨在考察我们对递归、树遍历...

    leetcode常见的100热点算法题

    例如,"Unique Paths"(不同路径)和"House Robber"(打家劫舍)都是经典的动态规划题目。 3. **回溯与深度优先搜索**:这类算法通常用于解决组合优化问题和图遍历问题。例如,"N-Queens"(八皇后问题)和"Word ...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, (Lintcode)564.Backpack VI 不适用 53....

    Leetcode部分试题解析

    18. **House Robber**:打劫问题。这是动态规划的应用,计算在不触动相邻房屋的情况下能偷窃的最大价值。 19. **Palindrome Linked List** 和 **Palindrome Number**:判断链表或数字是否为回文。链表可以用双指针...

    Roberry_house_dynamicprogramming_源码

    在这个场景中,"Roberry_house_dynamicprogramming_源码" 提到的是一个关于房屋盗窃问题的动态规划解决方案,通常被称为“House Robber”问题。这个问题源于LeetCode等在线编程挑战平台,旨在锻炼程序员的逻辑思维和...

    JAVA程序设计上机课4_阳甫军‘.pptx

    1. LeetCode 198:House Robber(打家劫舍) - 这是一个经典的动态规划问题,目标是确定在一个房子列表中,不相邻的房子可以被抢劫的最大金额。需要提交代码并附上运行结果截图。 2. LeetCode 349:Intersection ...

Global site tag (gtag.js) - Google Analytics