题目描述

198. 打家劫舍

题解

此题为经典的线性DP题目，DP题目，目前dp题目主要为以下几个步骤分析：

  1. 状态定义
  2. 转移方程
  3. 初始状态
  4. 返回值

状态定义

动态规划列表dp , dp[i]表示前 i 个房子在满足条件能偷窃到的最高金额,当前房子的价值为 num

转移方程

假设有 N 个房间，前 N 间能偷窃到的最高金额是 dp[n] , 前 N-1间房子能偷窃到的最高金额为dp[n-1],一个房间只会存在两个情况 ， 1 被偷 ， 0 没被偷 ，下面我们各自分析一下。

房间被偷

假设第 N 间房子被偷，由于相邻的房子不能被偷则 dp[N-1]不能被偷，由于房间的价值都是正值，偷得房间越多则价值更大，所以当N间被偷，dp[N-2]可偷 ， 所以则 dp[N] = max(dp[N-1],dp[N-2]+num)

房间没被偷

假设第 N 间房子没被偷则 dp[N] = dp[N-1]

合并两种情况转移方程为 dp[N] = max(dp[N-1],dp[N-2]+num)

初始状态

当N=0 没有房子则价值为 0 ，dp[0]=0

当N=1 只有一间房子 则 dp[1] = num

返回值

因房子的价值为正值，所以偷得房间越多则价值越大，所以最后一个房子的价值 dp[N] 即为最大值

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
        //经典线性dp ,  dp(i) = Math.max((dp(i-2)+nums[i-1]),dp(i-1) )  i>=2
        public int rob(int[] nums) {
            //临界条件
            if (nums == null || nums.length == 0) {
                return 0;
            }
            if (nums.length == 1) {
                return nums[0];
            }
            int n = nums.length;
            //此处为展示dp特性故用数组展示，空间复杂度为O(N)
            // 因只依赖前两个值，可以优化为两个变量O(1),此处暂不演示
            int[] dp = new int[n+1];
            dp[0] = 0;
            dp[1] = nums[0];
            int res = Math.max(dp[0], dp[1]);
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.max((dp[i - 2] + nums[i-1]), dp[i - 1]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }