526互联

213. 打家劫舍 II

发布时间 2023-07-04 17:28:54作者: 白露~

1. 题目

读题

 

 

考查点

 

2. 解法

思路

解法思路是这样的：

  • 由于房屋是环形排列的，所以不能同时偷第一个和最后一个房间，否则会触发报警。
  • 因此，可以将问题分成两个子问题，一个是不偷第一个房间，另一个是不偷最后一个房间。
  • 对于每个子问题，可以用动态规划的方法求解，定义一个数组表示从某个起点到某个终点的最大收益。
  • 对于每个位置，有两种选择，一种是偷这个房间，另一种是不偷这个房间。如果偷这个房间，那么就不能偷前一个房间；如果不偷这个房间，那么就可以偷前一个房间。
  • 因此，可以用一个状态转移方程来表示这个选择，即 f[i] = max(f[i - 1], f[i - 2] + nums[i]) ，其中 f[i] 表示从起点到第 i 个房间的最大收益，nums[i] 表示第 i 个房间的金额。
  • 最后，比较两个子问题的最大收益，取较大值作为答案。

 

代码逻辑

  1. 打家劫舍 II 是一个动态规划的问题，主要思路是将环形数组分成两个单排数组，分别求解最大收益，然后取两者的较大值。具体步骤如下：
  • 如果数组长度为1，直接返回第一个元素的值。
  • 如果数组长度为2，返回两个元素中的较大值。
  • 定义两个数组 f[] 和 g[] ，分别表示从第一个元素到倒数第二个元素，和从第二个元素到最后一个元素的最大收益。
  • 初始化 f1 = nums[0] ， g2 = nums1 。
  • 从 i = 2 到 n - 1 ，更新 f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]) 。
  • 从 i = 3 到 n ，更新 g[i] = max(g[i - 1], g[i - 2] + nums[i - 1]) 。
  • 返回 max(f[n - 1], g[n]) 。

具体实现

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0]; //只有一间房间，返回nums[0]
        if (n == 2) return Math.max(nums[0], nums[1]); //只有两间房间，返回较大值
        int[] f = new int[n + 1], g = new int[n + 1]; //定义两个数组
        f[1] = nums[0]; //初始化
        g[2] = nums[1];
        for (int i = 2; i <= n - 1; i++) {
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]); //更新f[i]
        }
        for (int i = 3; i <= n; i++) {
            g[i] = Math.max(g[i - 1], g[i - 2] + nums[i - 1]); //更新g[i]
        }
        return Math.max(f[n - 1], g[n]); //返回最大值
    }
}

 

自有实现

public class HouseRobII {

    public static void main(String[] args) {
        int[] nums =  {1,2,3,1};
        System.out.println(rob(nums));
    }

    public static int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);

        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];

        dp1[1] = nums[0];
        dp2[2] = nums[1];

        for (int i = 2; i <= n - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i-1]);
        }

        for (int i = 3; i <= n; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i-1]);
        }

        return Math.max(dp1[n - 1], dp2[n]);
    }

}

 

 

 

 

3. 总结