1. 问题
在一条直线上, 有 n 个房屋, 每个房屋中有数量不等的财宝, 有一个盗 贼希望从房屋中盗取财宝, 由于房屋中有报警器, 如果同时从相邻的两个房屋中盗取财宝就会触发报警器. 问在不触发报警器的前提下, 最多可获取多少财宝? 例如 [5,2,6,3,1,7], 则选择 5,6,7.
2. 示例
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) , 然后偷窃 3 号房屋 (金额 = 3).
偷窃到的最高金额 = 1 + 3 = 4 .
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9), 接着偷窃 5 号房屋 (金额 = 1).
偷窃到的最高金额 = 2 + 9 + 1 = 12 .
3. 思路
对于此题, 如果只有两家或者以下, 我们选择金额最大的. 如果 2 家以上, 那我们打劫到第 i 家的时候, 就要考虑, 要不要打劫这一家, 也就是 (这一家的价值 + 打劫到 i - 2 家的最大价值) 和(打劫到上一家 (i - 1) 的最大价值), 比较这两个值, 选较大值作为打劫到第 i 家的最大价值. 最后输出最后一家就可以了.
4. 代码实现
- package com.emotiv.code;
- /**
- * @Author: JLU Tiger
- * @Date: 2019/11/22 9:26
- */
- public class Answer {
- public static int rob(int[] nums) {
- if (nums.length == 0) return 0;
- int[] dp = new int[nums.length];
- dp[0] = nums[0];
- // 每次做数组判定时都需要做数组边界判定, 防止越界
- if (nums.length == 1) return nums[0];
- if (nums.length == 2) return Math.max(nums[0], nums[1]);
- // 当两家以上时, 打劫到第 i 家的时候, 就要考虑要不要打劫这一家, 也就是(这一家的价值 + 打劫到 i-2 家的最大价值)
- // 和(打劫到 i-1 家的最大价值), 比较这两个值, 选较大值作为打劫到 i 的最大值
- for (int i = 2; i <nums.length; i++) {
- dp[i] = ((nums[i] + dp[i - 2])> dp[i - 1]) ? (nums[i] + dp[i - 2]) : dp[i - 1];
- }
- return dp[nums.length - 1];
- }
- public static void main(String[] args) {
- int[] nums = {1,2,3,1};
- System.out.println(rob(nums));
- }
- }
来源: http://www.bubuko.com/infodetail-3298519.html