后端开发刷题 | 打家劫舍

描述

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。

给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

数据范围：数组长度满足 1≤n≤2×105，数组中每个值满足 1≤num[i]≤5000

示例1

输入：

[1,2,3,4]

返回值：

6

说明：

最优方案是偷第 2，4 个房间   

示例2

输入：

[1,3,6]

返回值：

7

说明：

最优方案是偷第 1，3个房间   

示例3

输入：

[2,10,5]

返回值：

10

说明：

最优方案是偷第 2 个房间  

思路分析：

该题使用动态规划来解决，

具体做法：

• step 1：用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
• step 2：（初始状态） 如果数组长度为1，只有一家人，肯定是把这家人偷了，收益最大，因此dp[1]=nums[0]。
• step 3：（状态转移） 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的i在dp中为数组长度，在nums中为下标。

图示：

代码：

import java.util.*;


public class Solution {
    /**
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        int[] dp=new int[nums.length+1];
        dp[1]=nums[0];
        for(int i=2;i<=nums.length;i++){
            dp[i]=Math.max(dp[i-1],nums[i-1]+dp[i-2]);
        }
        return dp[nums.length];
    }
}