動态規劃總結打家劫舍

打家劫舍1

題目

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。

示例1:

輸入：[1,2,3,1]

輸出：4

解釋：偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。

  偷竊到的最高金額 = 1 + 3 = 4 。

示例2:

輸入：[2,7,9,3,1]

輸出：12

解釋：偷竊 1 号房屋 (金額 = 2), 偷竊 3 号房屋 (金額 = 9)，接着偷竊 5 号房屋 (金額 = 1)。

  偷竊到的最高金額 = 2 + 9 + 1 = 12 。

解題思路

打家劫舍的問題是用動态規劃解決的經典問題。

首先第一步：确定 dp 數組以及下标的含義，dp[i]：考慮下标i（包括i）以内的房屋，最多可以偷竊的金額為dp[i]。

第二步确定遞推公式：

如果偷第i房間，那麼dp[i] = dp[i - 2] + nums[i]，因為不能再考慮第i-1間房，是以最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。

如果不偷第i房間，那麼dp[i] = dp[i - 1]。

然後dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

第三步，dp 數組初始化：從dp[i]的定義上來講，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

第四步，确定周遊順序：dp[i] 是根據dp[i - 2] 和 dp[i - 1] 推導出來的，那麼一定是從前到後周遊！

代碼實作

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int length = nums.length;
        if(length == 1){
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

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

複雜度分析

• 時間複雜度：O(n)，其中 n 是數組長度。隻需要對數組周遊一次。
• 空間複雜度：O(1)。

打家劫舍2

題目

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

示例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,6,1,9,1], 我們考慮的情況就是下标從1~3的情況，也就是[6,1,9];

情況二：考慮包含首元素，不包含尾元素

例如，數組 [1,6,1,9,1], 我們考慮的情況就是下标從0~3的情況，也就是[1,6,1,9];

情況三：考慮包含尾元素，不包含首元素

例如，數組 [1,6,1,9,1], 我們考慮的情況就是下标從1~4的情況，也就是[6,1,9,1];

由于情況一已經被情況二和三所包含，是以我們在求解的時候，隻需要包含後倆種情況即可。

代碼實作

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];

        // 包含首元素，不包含尾元素
        int value1 = RobRange(nums, 0, nums.length-2);
        // 包含尾元素，不包含首元素
        int value2 = RobRange(nums, 1, nums.length-1);

        return Math.max(value1, value2);
    }

    public int RobRange(int[] nums, int start, int{
        if(start == end) return nums[start];
        int[] dp = new int[nums.length];

        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start+1]);

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

        return      

複雜度分析

• 時間複雜度：O(n)，其中 n 是數組長度。
• 空間複雜度：O(1)。

1. 閱讀完記得給我點個贊哦，有👍 有動力
2. 關注公衆号---HelloWorld傑少，第一時間推送新姿勢