题解 | #打家劫舍(二)#

题意整理

给定n个房子排成一圈，每个房子都有一定现金。
现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。

方法一（动态规划）

1.解题思路

状态定义： $d p [i]$ 表示到第i个房间为止，能偷到的最多的现金。
状态初始化：到第0个房间时，最多偷第0个房间的现金。到第1个房间时，最多偷第0个房间或第1个房间的现金，两者中取较大者。
状态转移：要么是前前家+当前，要么是前一家，取较大者。即 $d p [i] = M a t h . m a x (d p [i - 1], d p [i - 2] + n u m s [i])$ 。

首先在nums的0到n-2的房子中找，然后在1到n-1的房子中找，取两者中的较大者。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        int n=nums.length;
      	//在0到n-2范围内找
        int rob1=getRob(Arrays.copyOfRange(nums,0,n-1));
        //在1到n-1范围内找
        int rob2=getRob(Arrays.copyOfRange(nums,1,n));
        
        return Math.max(rob1,rob2);       
    }
    
    private int getRob(int[] nums){  
        int n=nums.length;
        //边界情况处理
        if(n==0) return 0;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        //定义dp数组
        int[] dp=new int[n];
        //初始化
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            //状态转移
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

3.复杂度分析

时间复杂度：最多遍历所有房间两次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外大小为n的dp数组，所以空间复杂度为 $O (n)$ 。

方法二（迭代）

1.解题思路

定义两个变量，一个记录到前前家为止最多偷多少，一个记录到前一家为止最多偷多少。
遍历所有的房间，要么是前前家+当前，要么是前一家，取较大者。

同方法一的思路相似，首先在nums的0到n-2的房子中找，然后在1到n-1的房子中找，取两者中的较大者。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        int n=nums.length;
        //在0到n-2范围内找
        int rob1=getRob(nums,0,n-1);
        //在1到n-1范围内找
        int rob2=getRob(nums,1,n);
        
        return Math.max(rob1,rob2);       
    }
    
    private int getRob(int[] nums,int start,int end){       
        //记录到前前家为止最多偷多少
        int prepre=0;
        //记录到前一家为止最多偷多少
        int pre=0;
        int n=nums.length;
        for(int i=start;i<end;i++){
            //要么是前前家+当前，要么是前一家，取较大者
            int cur=Math.max(prepre+nums[i],pre);
            //状态后移
            prepre=pre;
            pre=cur;
        }
        return pre;
    }
}

3.复杂度分析

时间复杂度：最多遍历所有房间两次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。