打家劫舍 I

题目简介

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

代码模板

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

    }
};

问题分析

递归

我们以示例一为例，这条街区一共有四个房屋，我们可以从最后一个房屋（即第四个房屋）开始看。如果我们偷第四个房屋，那么第三个房屋我们就不能偷。如果我们不偷第四个房屋，那么第三个房屋就可以偷或者不偷。依次类推，直到我们推到第一个房屋。示例图如图所示：

通过观察我们可以知道，我们从第四个房屋一直推导到第一个房屋的过程中形成了一种二叉树的结构。我们想要求出我们能偷到的最大的钱数，只需要通过深度优先搜索(dfs)的方法遍历整棵树即可。dfs遍历的过程是通过递归实现的。我们通过“递”的过程从根节点（第四个房屋）遍历到了叶子节点（第0个房屋）。然后通过“归”的过程进行回溯，逐渐遍历整棵树，然后对能偷到的钱就行统计，就可以得到我们想要的结果。
这种方法虽然可以得到正确的结果，但是它的时间复杂度却很高。原因在于随着数据量的提升，这棵树的规模将会逐渐增大，程序的执行效率也会逐渐下降。另外，当我们对树进行遍历的过程中，产生了一些重复计算，这些重复计算也会随着数据量的提升而越来越多，这也是导致程序的时间复杂度上升的一个重要原因。

以下是递归实现的一个示例代码，该算法无法通过力扣的全部检查点。

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        return _rob(nums.size(),nums);
    }

private:
    int _rob(int k, vector<int> &_nums)
    {
        if(k<=0)
        {
            return 0;
        }

        int selected=_nums[k-1]+_rob(k-2,_nums); //不要忘记加上当前元素的值
        int unselected=_rob(k-1,_nums);
        return max(selected,unselected);
    }
};

记忆化搜索

正如上方所指出的那样，这个算法的时间复杂度较高的原因之一在于大量的重复计算。那么我们就需要对该算法进行优化，去除这些无效的运算。一个比较好的方法是我们可以引入一个数组"memo"，在每次进行运算时记录当前节点的结果。当我们之后遇到重复的计算时，只需要从"memo"数组中找出相应的结果就行了。

从算法的时间复杂度和空间复杂度的角度来看，这是一种用“空间”换“时间”的方法，我们之前通过使用一部分内存来对结果进行存储，这样CPU需要获得相应的结果的时候只需要从内存中取出之前计算的结果就行了，就不需要再浪费一部分时间来进行相应的计算了。

从上方构建本问题的二叉树的角度来看，这种方法实现了对二叉树的“剪枝”，从而减少了遍历所需要的时间，大大降低了算法的时间复杂度。这种方法叫做记忆化搜索，掌握记忆化搜索的基本思路有利于我们以后使用动态规划来解决问题，因为动态规划也是通过存储重叠子问题的解的方式来提升时间效率的。

本问题的记忆化搜索实现代码如下，该算法能通过力扣的所有检查点：

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        vector<int> memo(nums.size(),-1);
        return _rob(nums.size(),nums,memo);
    }

private:
    int _rob(int k, vector<int> &_nums, vector<int> &_memo)
    {
        if(k<=0)
        {
            return 0;
        }
        if(_memo[k-1]!=-1)
        {
            return _memo[k-1];
        }

        int selected=_nums[k-1]+_rob(k-2,_nums,_memo);
        int unselected=_rob(k-1,_nums,_memo);
        _memo[k-1]=max(selected,unselected);
        return _memo[k-1];
    }
};

初识动态规划 —— 递推关系与状态转移方程

动态规划是一种将问题拆分成一系列小问题的一种解决问题的方法。利用动态规划解决问题时，除了对于动态规划的基本方法的理解以外，更多的还要针对具体问题进行具体分析，思考如何将一个大的问题拆分成几个互不重叠的小问题，列出它的状态转移方程，从而根据它的递推关系一步步地解决这个较大的问题。
针对本问题，我们可以进行下面的分析：

假设只有一个房子，那么想要偷到最大的钱数，我们只需要偷这一个房子就行了，那么 result=nums[0]; 。

假设有两个房子，我们想要偷到最大的钱数，就只能偷其中的钱数最多的那个房子，而另一个房子并不能偷。因为对于两个房子而言，它们一定是相邻的，如果两个房子都偷的话，则会触发警报，这并不满足问题的要求。那么本问题的结果就是 result=max(nums[0],nums[1]);。

假设有三个房子，对于第三个房子，如果我们偷的话，就不能偷第二个房子，只能偷第一个房子。如果不偷的话，我们就可以选择偷第二个房子或者不偷第二个房子，具体偷不偷取决于是否能让我们得到最大的钱数。（不一定非要偷第二个房子才能获得最大的钱数，因为偷了第二个房子就代表偷不了第一个房子，这也是我们需要考虑偷不偷第二个房子的原因）。

对于四个及以上的房子，也是和三个房子同理的。我们将上方的memo数组转换为dp数组。就可以得到以下的递推关系：result=dp[n-1]=max(dp[n-2],nums[n-1]+dp[n-1])；。

这个递推关系就叫做动态规划的状态转移方程。与之前的方法不同的是，这个从“偷一个房子”(小问题)逐步推导，直到推到我们想要的结果“偷n个房子”(大问题)的。因此我们可以通过写一个for循环，来从dp[0]逐步推导至dp[n-1]，从而得到我们想要的结果。
这种方法的优势一在于dp数组也像memo数组一样，通过存储之前已有的状态来避免对于重叠子问题的重复计算。二在于不同于递归的自顶而下，自根节点遍历到每个叶子结点的方法。这种方法是自底而上，自叶子节点向根节点来解决问题的，它去除了递归过程的“递”的过程，只保留了“归”的过程，这使得它并不需要遍历整棵树就可以得到我们想要的结果，从而大大提高了算法的时间效率。
本算法的一个实现代码如下，该算法能通过力扣的所有检查点：

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1)
        {
            return(nums[0]);
        }
        else if(nums.size()==2)
        {
            return(max(nums[0],nums[1]));
        }
        else
        {
            vector<int> dp(nums.size());
            dp[0]=nums[0];
            dp[1]=max(nums[0],nums[1]);
            for(int cptime=3;cptime<=nums.size();cptime++)
            {
                dp[cptime-1]=max(dp[cptime-2],dp[cptime-3]+nums[cptime-1]);
            }
            return dp.back();
        }
    }
};

dp[0]=nums[0]; //只有一个房子就只能偷这个房子
dp[1]=max(nums[0],nums[1]); //对于两个房子而言，偷钱数最多的那个房子

打家劫舍 II

题目简介

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

问题分析

本问题与 打家劫舍I 唯一的不同在于房子连成了环。这导致第一个房子和最后一个房子从本来不紧挨的状态变成了紧挨的状态，进而导致偷了第一个房子后就不能偷最后一个房子，偷了最后一个房子就不能偷第一个房子。所以我们只需要对这两种情况进行分类讨论并列出不同的状态转移方程即可。

假设偷第一家：

边界条件：

stoleone_dp[0]=nums[0]; //只有一家就偷这一家
stoleone_dp[1]=nums[0]; //有两家就只能偷第一家

该情况下的状态转移方程：

if(cptime==number)
{
stoleone_dp[cptime-1]=stoleone_dp[cptime-2]; //不偷最后一家
}
else
{
stoleone_dp[cptime-1]=max(nums[cptime-1]+stoleone_dp[cptime-3],stoleone_dp[cptime-2]); //非最后一家的情况下的状态转移方程，和打家劫舍I类似
}

假设不偷第一家：

边界条件：

unstoleone_dp[0]=0; //只有一家就不偷
unstoleone_dp[1]=nums[1]; //对于两家而言，第一家不偷了，那么可以选择偷第二家或者不偷第二家。但是要使得偷到的钱数最多，只能偷第二家。

该情况下的状态转移方程：

unstoleone_dp[cptime-1]=max(nums[cptime-1]+unstoleone_dp[cptime-3],unstoleone_dp[cptime-2]); //对于非第一家和第二家的状态转移方程，和打家劫舍I类似

最终，我们只需要对这两种分类讨论的情况取最大值即可：

return max(stoleone_dp[number-1],unstoleone_dp[number-1]);

完整代码实现

class Solution {
public:
    int rob(vector<int>& nums) {
        int number=nums.size();
        if(number==1)
        {
            return nums[0];
        }
        else if(number==2)
        {
            return max(nums[0],nums[1]);
        }
        else
        {
            vector<int> stoleone_dp(number,0);
            //偷第一家
            stoleone_dp[0]=nums[0];
            stoleone_dp[1]=nums[0];
            for(int cptime=3;cptime<=number;cptime++)
            {
                if(cptime==number)
                {
                    stoleone_dp[cptime-1]=stoleone_dp[cptime-2];
                }
                else
                {
                    stoleone_dp[cptime-1]=max(nums[cptime-1]+stoleone_dp[cptime-3],stoleone_dp[cptime-2]);

                }
            }
            //不偷第一家
            vector<int>unstoleone_dp(number,0);
            unstoleone_dp[0]=0;
            unstoleone_dp[1]=nums[1];
            for(int cptime=3;cptime<=number;cptime++)
            {
                unstoleone_dp[cptime-1]=max(nums[cptime-1]+unstoleone_dp[cptime-3],unstoleone_dp[cptime-2]);
            }
            int sum=max(stoleone_dp[number-1],unstoleone_dp[number-1]);
            return sum;
        }
    }
}; 

打家劫舍 III —— 树形动态规划

题目简介

问题分析

本问题与之前的问题不同点在于各个房屋之间形成了一棵二叉树。但我们依然可以用动态规划的思想来解决本问题：

状态转移：我们可以用树的后序遍历来遍历整棵树，由于后序遍历是按照 左子树 —— 右子树 —— 根节点的顺序进行遍历的。如果我们在遍历树时引入dp数组进行记录的话，根节点则可以接受到来自其左子树和右子树所记录的信息，这样我们便达到了状态转移的目的。

同时，考虑到每个节点可能存在 选与不选 两种情况。因此，在记录能偷到的钱的最大值时也应该分为这两种情况进行分类讨论，从而保证状态转移的完成。

完整代码实现

class Solution {
public:
    int rob(TreeNode* root) {
        auto result=dfs(root);
        return max(result.first,result.second);
    }
    pair<int,int> dfs(TreeNode* node)
    {
        if(node==nullptr)
        {
            return {0,0};
        }
        pair<int,int>left=dfs(node->left);
        pair<int,int>right=dfs(node->right);

        int stole=node->val+left.second+right.second;
        int unstole=max(left.first,left.second)+max(right.first,right.second);
        return {stole,unstole};
    }
};