Leetcode-198 -- 打家劫舍 (动态规划)

2021/07/14 Algorithm 共 1315 字,约 4 分钟

动态规划,通过寻找状态转移方程、边界,将原问题分解为相对简单的子问题的方式求解复杂问题的方法。

题目 打家劫舍

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

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

示例 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 。

解题思路

1. 确定解题方式 — 动态规划

看到题目描述,可以得知第 n 间房屋可以得到的总金币与n-1,n-2房屋有关。那么这道题的就可以使用动态规划来做。

2. 寻找动态规划的状态转移方程、边界

  • 当房间 n 为1 or 2时,则只需要比对这两间房屋金币最大值即可,故,边界是 n < 2
  • 当 n 大于 2 时,则对于 k(k>2) 房屋,有两种选择
    • 选择偷这间房屋,则此刻可以得到的总金币为 dp[k-2] + nums[k]
    • 不偷这件房屋,则此刻可以得到的总金币为 dp[k-1]
  • 故,状态转移方程为:dp[k] = max(dp[k-2] + nums[k], dp[k-1])

3. 将思路映射到代码中

由于每次只需要用到dp[k-2], dp[k-1]两个值,因此可以不用创建 dp 数组,使用变量就能完成。

我用 n 代表不偷,即是走到上个房间时的最大收益,还没偷上个房间;m代表偷当前房间,即 n + nums[k]ans代表当前房间最大收益。

(由于还不会画图,所以用 log 方式展现过程)

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    if (nums.length === 0) return 0;
    // m 为 偷当前房屋的金币,初始化为 第一个房间 的金币
    // n 为 不偷当前房屋的金币,故 初始化为 0
    // ans 为走到当前房屋时,所偷到到总金币。
    let m = nums[0],
        n = 0,
        ans = nums[0];

    console.log(`当前偷取第1间房屋后`, { m, n, ans });
    for (let i = 1; i < nums.length; i++) {
        /**
         * 动态规划,状态转移公式为
         * dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
         * 转化为代码,就是  m = dp[i-2] + nums[i]; n =  dp[i-2]
         */
        console.log(`当前是第${i + 1}间房屋,金币数是${nums[i]}`);
        console.log(`走过这间房间时:`, { m, n, ans });
        m = n + nums[i];
        n = ans;
        ans = Math.max(m, ans);
        console.log(`走过这间房间后:`, { m, n, ans }, 'm = n + cur, n = ans, ans = max(m,n)');
        console.log('');
    }

    return ans;
};

文档信息

Search

    Table of Contents