LeetCode刷题笔记（House Robber）

最近xianggang有点不太平，作为一介平民只能衷心希望xianggang能尽快恢复平静，国家繁荣富强横扫一切敌对势力，正如毛主席曾说：“敌军围困万千重,我自岿然不动”。下面和大家分享一下刚刷的这道题吧！

题目如下：

题意分析：

给定一个表示每个房屋放有多少金钱的数组，在不触动报警系统的情况下（偷窃连着的两个房子即会触动报警系统），请问你最多能偷到多少钱？

方法一（记忆化搜索法）

本题的解题思路可通过如下递归树来表示

 对于本题的状态定义如下

对于本题的状态转移方程定义如下

很显然有大量的重叠子问题且有最优子结构存在，所以可以考虑用记忆化搜索的方法（自顶向下）予以解决，具体实现思路见代码与注释。

解题代码如下：

class Solution{
private:
    //用memo数组实现记忆化功能
    vector<int> memo;
    int findrob( vector<int>& nums, int index ){
        //递归终止条件
        if( index >= nums.size() ) return 0;
        //若memo[index]被计算过，则直接使用即可，避免重复计算
        if( memo[index] != -1)  return memo[index];

        //若memo[index]没被计算过，则先计算得到res后再赋值给memo[index]，以便后面使用
        int res = 0;
        for ( int i = index; i < nums.size(); i++ ) {
            res = max( res, nums[i] + findrob(nums, i+2) );
        }
        memo[index] = res;
        return res;
    }


public:
    int rob( vector<int>& nums ){
        //由于抢劫的区间是（0，nums.size()-1）,所以memo大小只需要初始化为n即可
        memo = vector<int>(nums.size(), -1);
        return findrob( nums, 0 );
    }
};

提交后的结果如下：

 

方法二（动态规划法）

考虑维护一个数组memo，用两次for循环自底向上依次记录偷到每个房子时，偷窃金额的最大值，其中外层循环 i 控制偷房子的范围，内层 for 循环控制在给定范围内偷房子的组合。最后返回 memo[0] 即可。

解题代码如下：

class Solution{
public:
    int rob( vector<int>& nums ){
        int n = nums.size();
        if( n == 0 ) return 0;
        vector<int> memo(n, -1);
        memo[n-1] = nums[n-1];
        //在[i,...n-1]范围内偷房子
        for (int i = n - 2; i >= 0; i--) {
            //考虑从j=i开始偷，依次遍历
            for (int j = i; j < n; j++) {
                memo[i] = max( memo[i], nums[j] + (j + 2 < n ? memo[j+2] : 0 ));
            }
        }

        return memo[0];
    }
};

提交后的结果如下：

 

 

 

日积月累，与君共进，增增小结，未完待续。

转载：https://blog.csdn.net/Vensmallzeng/article/details/99546616