本系列部落格是LeetCode刷題筆記。打家劫舍(House Robber)是LeetCode上比較典型的一個題目,涉及三道題,求在不觸動警報裝置的情況下,能夠偷竊到的最高金額,主要解題思想是動态規劃,将三道題依次進行記錄。
打家劫舍(House Robber)是LeetCode上比較典型的一個題目,涉及三道題,主要解題思想是動态規劃,将三道題依次記錄如下:
(一)打家劫舍
題目等級:198、House Robber(Easy)
題目描述:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
題意:你是一個專業的小偷,計劃偷竊沿街的房屋。每間房内都藏有一定的現金,影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統,如果兩間相鄰的房屋在同一晚上被小偷闖入,系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組,計算你在不觸動警報裝置的情況下,能夠偷竊到的最高金額。
解題思路:
本題實際就是典型的動态規劃問題,沿街的房屋依次決定每一家偷還是不偷為一個階段,用dp[i]表示前i家擷取的最高金額,第i階段的決策就是兩種:偷、不偷。則不難寫出以下狀态轉移方程:
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
從以上的遞推公式可以看出,第i個狀态隻和i-1和i-2兩個狀态有關,是以,也可以省略掉數組,隻維護兩個變量即可。
//解法一:動态規劃(數組)
class Solution {
public int rob(int[] nums) {
//典型的動态規劃問題,dp[i]=max(dp[i-1],dp[i-2]+nums[i])
//每個階段确定一家偷還是不偷,是以決策就是偷和不偷兩種
if(nums==null || nums.length==0)
return 0;
int len=nums.length;
int[] res=new int[len+1];
res[0]=0;
res[1]=nums[0];
for(int i=2;i<=len;i++){
res[i]=Math.max(res[i-1],res[i-2]+nums[i-1]); //狀态轉移
}
return res[len];
}
}
//解法二:動态規劃(維護兩個變量)
class Solution {
public int rob(int[] nums) {
//dp[i]表示前i家可以得到的最高金額,dp[i]=Max(dp[i-1],dp[i-2]+nums[i])
if(nums==null || nums.length==0)
return 0;
int first=0,second=0,res=0;
for(int i=0;i<nums.length;i++){
res=Math.max(first+nums[i],second);
first=second;
second=res;
}
return res;
}
}
(二)打家劫舍 II
題目等級:213、House Robber II(Medium)
題目描述:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
題意:你是一個專業的小偷,計劃偷竊沿街的房屋,每間房内都藏有一定的現金。這個地方所有的房屋都圍成一圈,這意味着第一個房屋和最後一個房屋是緊挨着的。同時,相鄰的房屋裝有互相連通的防盜系統,如果兩間相鄰的房屋在同一晚上被小偷闖入,系統會自動報警。
解題思路:
本題和上題基本類似,差別在于:所有的房子圍成一個圈,意味着首尾兩家也屬于相鄰。
基本思路當然還是動态規劃,可以劃分成兩種情況來做,以第一家是否被偷為依據分成兩個動态規劃問題,如果第一家偷,那麼從第一家到第n-1家求最大值(因為意味着最後一家一定不能偷);如果第一家不偷,那麼從第2家到第n家求最大值。最後再比較兩種情況的最大值即可。
class Solution {
public int rob(int[] nums) {
/*
思路:由于首尾也屬于相鄰,是以需要分别判斷,以第一家是否打劫分成兩個問題
第一家搶:最後一家一定不能搶,從第0個到len-2做動态規劃
第一家不搶:從1到len-1做動态規劃
然後比較找出最大值
*/
if(nums==null || nums.length==0)
return 0;
int len=nums.length;
if(len==1)
return nums[0];
int[] dp1=new int[len];
int[] dp2=new int[len+1];
//第一家搶
dp1[0]=0;
dp1[1]=nums[0];
for(int i=2;i<len;i++)
dp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);
//第一家不搶
dp2[0]=0;
dp2[1]=0;
for(int i=2;i<=len;i++)
dp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i-1]);
return Math.max(dp1[len-1],dp2[len]);
}
}
//維護兩個變量
class Solution {
public int rob(int[] nums) {
//打家劫舍II,房屋圍成一個圈
if(nums==null || nums.length==0)
return 0;
int len=nums.length;
if(len==1)
return nums[0];
//第一家偷,最後一家不偷
int first=0,second=0,res1=0;
for(int i=0;i<len-1;i++){
res1=Math.max(first+nums[i],second);
first=second;
second=res1;
}
//第一家不偷,則最後一家有可能偷
first=0;
second=0;
int res2=0;
for(int i=1;i<len;i++){
res2=Math.max(first+nums[i],second);
first=second;
second=res2;
}
return Math.max(res1,res2);
}
}
(三)打家劫舍 III
題目等級:337、House Robber III(Medium)
題目描述:
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
題意:在上次打劫完一條街道之後和一圈房屋後,小偷又發現了一個新的可行竊的地區。這個地區隻有一個入口,我們稱之為“根”。 除了“根”之外,每棟房子有且隻有一個“父“房子與之相連。一番偵察之後,聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫,房屋将自動報警。
解題思路:
和上兩題不同的是:本題是二叉樹形狀,樹中直接相連(也就是父子節點)不能同時打劫。
實際上,有上一題的經驗,我們不難找到規律:這裡可以按根結點是否打劫分為兩種情況,如果根結點被打劫,那麼意味着它的子節點都不能打劫,需要直接打劫其孫子輩節點;如果根結點不打劫,那麼可以考慮其左右孩子。同時,由于樹的特性,左右子樹都是子問題,是以實際上就是兩種情況分别遞歸。
class Solution {
public int rob(TreeNode root) {
/*
按根偷不偷,分兩種情況,分别遞歸
*/
if(root==null)
return 0;
int res1=0;
//根在結果中
res1+=root.val;
if(root.left!=null)
res1+=(rob(root.left.left)+rob(root.left.right));
if(root.right!=null)
res1+=(rob(root.right.left)+rob(root.right.right));
//根不在結果中
int res2=rob(root.left)+rob(root.right);
return Math.max(res1,res2);
}
}