一、题目

1、题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

2、基础框架

class Solution {
public:
    int rob(vector<int>& nums) {

    }
};

3、原题链接

198.打家劫舍

二、解题报告

1、思路分析

  （1）对于每个整数而言，可以选择取或者不取，所以共有 $2^n$ 种取法，但是相邻的数不能都取，所以方案数肯定是 $<2^n$，但是时间复杂度还是指数级的，所以暴力枚举会超时。
  （2）于是，使用动态规划。
    ①定义状态数组 $dp[i]$ 表示前 $i$ 个整数通过某种选取方案能够获得的最大值；

    ②如果第 $i$ 个整数不取，那么第 $i-1$ 个数及之前取或者不取都是可以的，于是转换为 $dp[i-1]$的子问题；
    ③如果第 $i$ 个整数取，则第 $i-1$ 个整数不能取，而第 $i-2$ 及之前的数取不取都是随意的，于是转换为 $dp[i-2]$ 的子问题
    ④最终，得到状态转移方程：$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$
    ⑤初始状态：$dp[0]=nums[0],dp[1]=max(nums[0],nums[1])$

2、时间复杂度

  $O(n)$

3、代码详解

class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[105];
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (i == 1) { //以防下标溢出，下标为1的情况单独处理
                dp[1] = max(nums[0], nums[1]);
            } else {
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            }
        }
        return dp[nums.size() - 1];
    }
};

4、复盘

这是一道基础线性DP题，之所以叫线性是因为状态数和时间复杂度呈线性关系，是 O(n) 的。

每个状态的状态转移的时间复杂度是 $O(1)$ ，那么什么是 $O(1)$ 呢？简单理解就是状态转移的时间与 $n$ 无关，这道题目中无论 $n$ 多大， $i$ 的状态一定是从 $i-1$ 或者 $i-2$ 转移过来的，所以每次状态转移最多两次计算。 $O(1)$ 的含义更多的是代表常数时间复杂度。

线性DP最大特征就是状态是用一个一维数组表示，一般状态转移的时间复杂度为 $O(1)$ 或 $O(n)$。

变种题目：740.删除并获得点数
解题报告：【Leetcode】198. 打家劫舍（中等）