​LeetCode刷题实战213:打家劫舍 II

程序IT圈

共 3622字,需浏览 8分钟

 ·

2021-03-17 13:59

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 打家劫舍 II,我们先来看题面:
https://leetcode-cn.com/problems/house-robber-ii/

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

题意

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

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

示例


示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

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

示例 3:

输入:nums = [0]
输出:0
 

提示:

1 <= nums.length <= 100
0 <= nums[i] <= 1000


解题

https://cloud.tencent.com/developer/article/1413039

此题为典型的动态规划问题,但是我们需要考虑几种特殊情况
此题为一个环,所以两端不可并行探索,所以分为两种情况,
第一种 探索   0 - (length - 2)
第二种 探索   1 - (length - 1)
在考虑只有长度为1或2的时候
综合考虑

接下来科普下动态规划思想

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。

简单来说,动态规划就是寻找每个阶段的最优解

那我们先按照第一种情况分析下(从0 到 length - 2)

假设我们进行测试的数组为
[3,1,5,12,6,8,13,2]
那我们探索
首先我们进行前两个的探索,然后每加一个数,进行两种情况的比较,选出局部最优解
【3,1】最优解为3  前最优解为3
【3,1,5】最优解为8 前最优解为3 【3 + 5】
【3,1,5,12】最优解为 3 + 12 = 15 > 8 最优解为 【3 + 12】前最优解为8
【3,1,5,12,6】最有解为 15 > 8 + 6 最优解为 【3 + 12】前最优解为 15
【3,1,5,12,6,8】最优解为 15 + 8 > 15 最优解为 【3 + 12 + 8】为23 前最优解为15
【3,1,5,12,6,8,13】最优解为 15 + 13 > 23 最优解为 【3 + 12 + 13】前最优解为23
【3,1,5,12,6,8,13,2】最优解为 28 > 23 + 2 最优解为 【3 + 12 + 13】

依次类推 保证每个阶段都有最优解

var rob = function(nums) {
    //特殊情况
    const len = nums.length
    if (len === 0) return 0
    if (len === 1) return nums[0]
    if (len === 2) return Math.max(nums[0], nums[1])
    
    const rob = function(nums, start, end) {
        let pMax = nums[start]
        let cMax = Math.max(pMax, nums[start + 1])
        
        for (let i = start + 2; i <= end; i++) {
            console.log(i,cMax,pMax)
            let tmp = cMax
            cMax = Math.max((pMax +nums[i]), cMax)
            pMax = tmp
        }
        
        return cMax
    }
    
    return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1))
};



好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-200题汇总,希望对你有点帮助!

LeetCode刷题实战201:数字范围按位与

LeetCode刷题实战202:快乐数

LeetCode刷题实战203:移除链表元素

LeetCode刷题实战204:计数质数

LeetCode刷题实战205:同构字符串

LeetCode刷题实战206:反转链表

LeetCode刷题实战207:课程表

LeetCode刷题实战208:实现 Trie (前缀树)

LeetCode刷题实战209:长度最小的子数组

LeetCode刷题实战210:课程表 II

LeetCode刷题实战211:添加与搜索单词

LeetCode刷题实战212:单词搜索 II


浏览 13
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报