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

题意整理

给定并排的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])$ 。

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)$ 。
空间复杂度：需要额外大小为n的dp数组，所以空间复杂度为 $O (n)$ 。

方法二（迭代）

1.解题思路

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

图解展示： alt

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 (1)$ 。