题目描述

1.打家劫舍Ⅰ

解题思路

• 考虑特殊情况：
  –当只有一间房时，ans=nums[0];
  – 当有两间房时，ans=max(nums[0],nums[1])；因为前两间房相邻，只能偷一家；
• 一般情况，即房间数>2时，此时用dp[i]表示前i间房的最大价值，对于第k间房：
  –偷，dp[k]=dp[k-2]+nums[k]；
  –不偷，dp[k]=dp[k-1]；
• 所以有状态转移方程：dp[i]=max(dp[i-1],dp[i-2]+nums[i])；
  代码展示

class Solution {
public:
/*
dp[i]表示窃取前i间房可取得的最大价值
与dp[i-2]+num[i],dp[i-1]
*/  
    int dp[105];
    int rob(vector<int>& nums) {
        int l=nums.size();
        if(l<2)return nums[0];
        dp[0]=nums[0],dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<l;i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[l-1];
    }
};

2.打家劫舍Ⅱ
解题思路

• 这题与Ⅰ的唯一不同就是第一间房与最后一间房相邻，即不能同时选择nums[0]与nums[l-1];
• 分析：
  –可以把数组分成两个区间[0,n-2]，[2,n-1]，求这两部分时不需要考虑首位相邻问题；¹
  –考虑一种特殊情况：
  
  代码展示

class Solution {
public:
/*
1.按照Ⅰ方法进行，可能会有同时选择0,l-1的情况
2.判断两个特殊情况：偷了第一家->第n家不能偷
                  
*/
    int Dp(vector<int>& nums,int l,int r){
        int f1=nums[l],f2=max(nums[l],nums[l+1]);
        for(int i=l+2;i<=r;i++){
            int temp=max(f2,f1+nums[i]);
            f1=f2;
            f2=temp;
        }
        return f2;
    }
    int rob(vector<int>& nums) {
        int l=nums.size();
        if(l==1)return nums[0];
        if(l==2)return max(nums[0],nums[1]);
        return max(Dp(nums,0,l-2),Dp(nums,1,l-1));
    }
};

3.打家劫舍Ⅲ

解题思路
（待更新~）

代码展示

---

1. 因为首尾必然不能同时选择 ↩︎