题目链接

打家劫舍

题目描述

image.png

实现代码

思路：其实爬楼梯类似，不过每次必须爬>1的楼梯；
记dp[i]表示有i家住户的情况能偷窃到的最大金额，可以知道结果只与前两个位置有关，相邻的位置不取第i个住户，中间隔了两个位置的偷窃第i个住户，则有状态转移方程：

dp[i] = min(dp[i-1], dp[i-2] + nums[i]);

实现代码如下：

  1. class Solution {
  2.     public int rob(int[] nums) {
  4.         int n = nums.length;
  6.         if(n == 1) {
  7.             return nums[0];
  8.         }
  10.         int[] dp = new int[n];
  11.         dp[0] = nums[0];
  12.         dp[1] = Math.max(nums[0], nums[1]);
  14.         for(int i=2; i<n; i++) {
  15.             dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
  16.         }
  18.         return dp[n-1];
  19.     }
  20. }