js-leetcode前端动态规划第 3 天打卡「打家劫舍」，一个函数解决两个问题

约定不等于承诺〃 2022-09-02 15:50 95阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center][]

## 198. 打家劫舍 ##

[198. 打家劫舍][198.]

### 解题思路 ###

明白这道题，「213. 打家劫舍 II」也就自然明白了。

首先，亮出 dp 状态方程

dp[i] = Math.max(dp[i-1], dp[i-2]+ nums[i]);

只有一家的时候，废话不多说，偷就完事了。

两家的话，对比一下，看哪一家有钱就偷哪家。

重点在于有三家以上的情况，对于这题来说，从第 2 家开始，如果偷这家，那就加上前两家的金钱（非累计）

如果不偷，就加上前一家的金钱（非累计）

看最后两家相邻的房屋累计的结果值最大

### 代码 ###

/**
     * @param {number[]} nums
     * @return {number}
     */
    var robValue = function(nums, left, right) {
        
        if(nums.length === 1) return nums[left];
        else if(nums.length ===2) return Math.max(nums[left], nums[right]);
        else {
        
            let dp = new Array(nums.length);
            dp[left] = nums[left];
            dp[left+1] = nums[left+1];
            // 从第 2 家开始，如果偷这家，那就加上前两家的金钱（非累计）
            // 如果不偷，就加上前一家的金钱（非累计）
            for(let i=left+1;i<=right;i++){
        
                // 边界条件
                if(i-2 < 0 || i-2 < left) dp[i-2] = 0;
                dp[i] = Math.max(dp[i-1], dp[i-2]+ nums[i]);
            }
            // 看最后两家相邻的房屋累计的结果值最大
            return Math.max(dp[right], dp[right-1]);
        }
    }
    
    var rob = function(nums) {
        
        return robValue(nums, 0, nums.length-1);
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70][]

## 213. 打家劫舍 II ##

### 解题思路 ###

这个和「198. 打家劫舍」对比来说，就多个条件。

那么，我们在上一题的基础上调用两次封装的函数就好了。

一次调用条件是去掉第一家，二次调用条件是去掉最后一家，这样就不会出现首尾都偷的情况了，最后我们比对最大值返回就好了。

/**
     * @param {number[]} nums
     * @return {number}
     */
    var robValue = function(nums, left, right) {
        
        if(nums.length === 1) return nums[left];
        else if(nums.length ===2) return Math.max(nums[left], nums[right]);
        else {
        
            let dp = new Array(nums.length);
            dp[left] = nums[left];
            dp[left+1] = nums[left+1];
            // 从第 2 家开始，如果偷这家，那就加上前两家的金钱（非累计）
            // 如果不偷，就加上前一家的金钱（非累计）
            for(let i=left+1;i<=right;i++){
        
                // 边界条件
                if(i-2 < 0 || i-2 < left) dp[i-2] = 0;
                dp[i] = Math.max(dp[i-1], dp[i-2]+ nums[i]);
            }
            // 看最后两家相邻的房屋累计的结果值最大
            return Math.max(dp[right], dp[right-1]);
        }
    }
    var rob = function(nums) {
        
        if(nums.length === 1) return nums[0];
        else if(nums.length === 2) return Math.max(nums[0], nums[1]);
        else {
        
            return Math.max(robValue(nums, 0, nums.length-2), robValue(nums, 1, nums.length-1));
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70 1][]

## 740. 删除并获得点数 ##

### 解题思路 ###

这个转换了之后和「打家劫舍」的题型就差不多了，原理都是捞最多的价值，但是左右不能相邻捞，因此可以将数据重复值通过索引数组来存，具体做法如下：

let maxLen = Math.max.apply(null, nums);
    // 创建索引数组
    let arr = new Uint32Array(maxLen+1);
    nums.map(item => arr[item]++);

之后，开始「打家劫舍」。

也是分两种情况：

*  如果当前户人家要偷的话，那就得加上前面两家（非累计）获得金钱，但本题不同的是，因为数据有重复项，由于之前处理过索引值，因此直接将当前索引与值相乘即可。
 *  如果当前户人家不偷的话，那就加上前一家（非累计）获得金钱。

数据量 `10^4`，在暗示我们用动态规划了。

状态方程如下，从第 2 家开始

dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]*i);

/**
     * @param {number[]} nums
     * @return {number}
     */
    var deleteAndEarn = function(nums) {
        
        let maxLen = Math.max.apply(null, nums);
        // 创建索引数组
        let arr = new Uint32Array(maxLen+1);
        nums.map(item => arr[item]++);
        // 开始「打家劫舍」
        let dp = new Array(arr.length);
        dp[0] = arr[0];
        dp[1] = arr[1];
        for(let i=1;i<arr.length;i++){
        
            if(i-2 < 0) dp[i-2] = 0;
            dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]*i);
        }
        return dp[arr.length-1];
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70 2][]

学如逆水行舟，不进则退

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/96d754aedf1e4903b74cfea4f6b8e152.png
[198.]: https://leetcode-cn.com/problems/house-robber/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70]: /images/20220829/e451040ac5dc4d45b546d478d21529ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70 1]: /images/20220829/0f9192cece29461e9e153909827391ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQyOTcxOA_size_16_color_FFFFFF_t_70 2]: /images/20220829/5183ba2cbc064a50baa46d193ad659d9.png