Leetcode-213-打家劫舍II

Leecode-213-House Robber II

思路：动态规划

题目描述：

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

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

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

这里在Leetcode198打家劫舍的基础上进行了条件追加：

本质上：其实就是分成两个问题

• 在不偷窃第一个房子的情况下，求出最大可以抢的金额p1
• 在不偷窃最后一间房子的情况下，求出最大可以抢的金额p2
• 比较p1和p2。取最大值

Solution：动态规划

• 思路：环状排列意味着第一个房子和最后一个房子中只能选出一个进行偷窃

• 状态定义：设动态规划列表 dp ，dp[i] 代表前 i个房子在满足条件下的能偷窃到的最高金额。

• 初始状态

  dp[0] = 0;
  dp[1] = nums[0];

• 状态转移方程：

dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);

• 返回值

返回dp数组的最后一个元素即为结果
return dp[len];
return dp[-1];

• 最终返回值

// 分割成两个子问题
// 1. 最后一家不偷情况下的金额
// 2. 第一家不偷情况下的金额
// 3. 取最大值
return Math.max(
    rob_helper(Arrays.copyOfRange(nums,0,nums.length-1))  // nums[0,n-1]
    ,rob_helper(Arrays.copyOfRange(nums,1,nums.length)));  // nums[1,n]

Java

Solution :

class Solution{
    public int rob_helper(int[] nums){
        int len = nums.length;
        if (len == 0){
            return 0;
        }

        // dp数组的长度是nums数组的长度加1
        // 因为dp[0] = 0
        int[] dp = new int[len + 1];

        // dp数组初始化
        dp[0] = 0;
        dp[1] = nums[0];

        // 状态转移方程
        for(int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        // 返回dp数组的最后一个元素即为结果
        return dp[len];
    }

    public int rob(int[] nums){
        int len = nums.length;
        if (len == 0){
            return 0;
        }
        if (len == 1){
            return nums[0];
        }
        return Math.max(rob_helper(Arrays.copyOfRange(nums,0,nums.length-1)),rob_helper(Arrays.copyOfRange(nums,1,nums.length)));
    }
}

测试用例：

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

• 时间复杂度：O(n)，遍历一次nums需要的时间。
• 空间复杂度：O(n)，需要额外的dp数组的空间。

Python

Solution :

打赏