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

题意整理

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

方法一（动态规划）

1.解题思路

• 状态定义：$dp[i]dp[i]$表示到第i个房间为止，能偷到的最多的现金。
• 状态初始化：到第0个房间时，最多偷第0个房间的现金。到第1个房间时，最多偷第0个房间或第1个房间的现金，两者中取较大者。
• 状态转移：要么是前前家+当前，要么是前一家，取较大者。即$dp[i]=Math\mathrm{.}max(dp[i-1],dp[i-2]+nums[i])dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i])$。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (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)O(n)$。
• 空间复杂度：需要额外大小为n的dp数组，所以空间复杂度为$O(n)O(n)$。

方法二（迭代）

1.解题思路

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

图解展示：

2.代码实现

import java.util.*;

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

3.复杂度分析

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