数据结构与算法之动态规划: 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.length
  if(len === 0) return 0
  if(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;
};