算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从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此题为典型的动态规划问题，但是我们需要考虑几种特殊情况此题为一个环，所以两端不可并行探索，所以分为两种情况，动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。那我们先按照第一种情况分析下(从0 到 length - 2)首先我们进行前两个的探索，然后每加一个数，进行两种情况的比较，选出局部最优解【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))
};
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
