【力扣刷題第十天-2】 打家劫舍

文章目錄

• 前言
• 一、題目描述
• 二、解題思路
• 三、示例代碼

前言

  本題主要考查 動态規劃 算法。

提示：以下是本篇文章正文内容，程式設計語言為Java

一、題目描述

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

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

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 号房屋 (金額 = 1) ，然後偷竊 3 号房屋 (金額 = 3)。
     偷竊到的最高金額 = 1 + 3 = 4 。
           

連結：打家劫舍

二、解題思路

  1）确定dp數組的含義。 我們用

dp[i]

表示小偷前

i

間房所能偷竊到的最高金額

  2）推導狀态轉移方程。 對于第

i

間房，小偷可以選擇偷或不偷。當選擇偷這間房，第

i-1

間房就不能偷，是以

dp[i] = dp[i-2] + num[i]

；當選擇不偷，偷竊總金額為前

i−1

間房屋的最高總金額

dp[i] = dp[i-1]

。

  3）分析邊界條件。 當隻有一間房時，則選擇偷竊此房，即

dp[0] = num[0]

；當隻有兩間房時，需要選擇金額較多的偷，即

dp[1] = max(num[0], num[1])

.

三、示例代碼

class Solution {
    public int rob(int[] nums) {
       
        if(nums.length==1) return nums[0];
        int dp[]=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
      return dp[nums.length-1];
    }
    
}