数据结构与算法之动态规划: LeetCode 213. 打家劫舍 II (Ts版)

打家劫舍 II

• https://leetcode.cn/problems/house-robber-ii/description/

描述

• 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金
• 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的
• 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
• 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额

示例 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 = [1,2,3]
输出：3

提示

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

Typescript 版算法实现

1 ) 方案1:动态规划

function rob(nums: number[]): number {const n = nums.length;if (n === 0) return 0;if (n === 1) return nums[0];// dp1 不抢最后一个房子, dp2 不抢第一个房子const dp1: number[] = new Array(n).fill(0);const dp2: number[] = new Array(n).fill(0);dp1[0] = nums[0];dp1[1] = Math.max(nums[0], nums[1]);dp2[1] = nums[1];for (let i = 2; i < n; ++i) {dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);}// 对于 dp2，我们从第二个元素开始计算，因此需要单独处理for (let i = 2; i < n - 1; ++i) {dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);}return Math.max(dp1[n - 2], dp2[n - 1]);
}

2 ) 方案2:动态规划

function rob(nums: number[]): number {const len = nums.lengthif(len === 0) return 0if(len === 1) return nums[0]const ret1 = robRange(nums,0,len-2)const ret2 = robRange(nums,1,len-1)return Math.max(ret1,ret2)
};function robRange(nums,start,end) {if(end === start) return nums[start]const dp = new Array(nums.length).fill(0)dp[start] = nums[start]dp[start+1] = Math.max(nums[start],nums[start+1])for(let i=start+2; i<=end; i++) {dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1])}return dp[end]
}

3 ) 方案3: 动态规划优化版

function rob(nums: number[]): number {const length = nums.length;if (length === 1) {return nums[0];} else if (length === 2) {return Math.max(nums[0], nums[1]);}return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
}const robRange = (nums, start, end) => {let first = nums[start], second = Math.max(nums[start], nums[start + 1]);for (let i = start + 2; i <= end; i++) {const temp = second;second = Math.max(first + nums[i], second);first = temp;}return second;
}

4 ) 方案4: 递归版

function rob(nums: number[]): number {const n = nums.length;return Math.max(nums[0] + helper(nums.slice(2, n - 1)), helper(nums.slice(1)))
};function helper (nums) {let f0 = 0, f1 = 0;for (const x of nums) {[f0, f1] = [f1, Math.max(f1, f0 + x)]}return f1;
};