【刷算法】LeetCode.198-打家劫舍

whinc 发布于2019-08-23 14:08 / 319人阅读

摘要：你是一个专业的小偷，计划偷窃沿街的房屋。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。示例输入输出解释偷窃号房屋金额，然后偷窃号房屋金额。偷窃到的最高金额。

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 0)
        return 0;
    if(nums.length === 1)
        return nums[0];
    
    let prepre = nums[0], pre = Math.max(nums[0], nums[1]);
    
    for(let i = 2;i < nums.length;i++) {
        let temp = pre;
        pre = Math.max(prepre + nums[i], pre);
        prepre = temp;
    }
    
    return pre;
};

云服务器 GPU云服务器刷应用刷VPS 刷cdn 刷alexa

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100150.html

【算法解析LeetCode by Javascript】213. 打家劫舍 II

摘要：偷窃到的最高金额。世纪年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法动态规划。 showImg(https://segmentfault.com/img/bVbplM3?w=953&h=465); 题目描述你是一个专业的小偷，计划偷窃沿街的房屋，每间房...

crelaber 2019-08-23 15:39 评论0 收藏0
面试常遇的打家劫舍问题你学会了吗~

摘要：打家劫舍打家劫舍问题描述问题描述你是一个专业的小偷，计划偷窃沿街的房屋。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。和分别表示的左右孩子。打家劫舍I问题描述你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报...

不知名网友 2021-11-25 09:43 评论0 收藏0
leetcode 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...

jzman 2019-08-16 11:06 评论0 收藏0
leetcode198,213 house robber

摘要：你不能连着偷两家因为这样会触发警报系统。现在有一个数组存放着每一家中的可偷金额，问可以偷的最大金额为多少这里考验了动态编程的思想。动态编程要求我们将问题一般化，然后再找到初始情况开始这个由一般到特殊的计算过程。 House Robber I You are a professional robber planning to rob houses along a street. Each...

whidy 2019-08-16 11:01 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0