198.打家劫舍.md

// 复习
// 此题应该是贪心算法or动态规划都能做。但按我的归纳，动态规划毕竟有固定套路，所以相对好做一点，贪心算法
// 则更类似脑筋急转弯，考虑一次遍历过程的局部最优，不太好想到。

// 看到题干应该想到可能是局部最优贪心算法，遍历所有得到最高金额又想到动态规划dp[i]的含义。这里就不再详细
// 赘述动态规划的思想，如果复习可以回顾“爬楼梯”。

// dp[i]含义：遍历到i时，偷窃到的最高金额就是dp[i]，i=0就是dp[0]，i=n-1就是dp[n-1]，这点思想要会。
// 递推公式：考虑例2：[2 7 9 3 1]，如果此时遍历到最后一个元素，dp[i]（即dp[4]）该如何递推。这是本题的核心
// 思想，既然不能相邻偷，那么要至少隔一个偷，那么dp[i]=dp[i-2]+nums[i]就是情况之一；那隔两个偷是否可以呢？
// 经过思考，也是可以的，比如[100 1 2 100]，这种显然就是隔两个偷钱最多；那么dp[i]=dp[i-3]+nums[i]又是
// 情况之一；此时，很容易误以为自己已经考虑完了，就去初始化dp[0]、dp[1]、dp[2]，让for循环从i=3开始遍历。
// 实际上还有一种情况，那就是如果如例1：[1 2 3 1]，最大值为1+3=4，i为最后一个时，dp[i]取的是dp[i-1]的值，
// 所以dp[i]=dp[i-1]也是一种情况。

// [注意]：此题这种解法想复杂了，建议看之前的解法即可。
// 实际上，只需要关注dp=max(dp[i-2]+nums[i],dp[i-1])这两个数的大小。为啥呢？因为当考虑末尾dp[i]时，假如
// [100 2 3 100]，其最后偷的一家只有两种情况。一是偷的i-1，则此时dp[i]=dp[i-1]；二是偷的i自己，则此时
// dp[i]=nums[i]+dp[i-2]，那为啥不用考虑dp[i-3]呢？因为，其实dp[i-2]已经把dp[i-3]考虑了，想想[1 2 3 1]
// 可以说dp[i-3]<=dp[i-2]恒成立，你都往后再偷一家了，难不成你往后的dp[i-2]还能比往前的dp[i-3]小？
// 偷到i-2时，要么偷的i-2，则dp[i-2]>dp[i-3]，因为此时多了一种偷法（两种：最后一步偷i-2or偷i-3，此时
// 多了最后一步偷i-2的方法），如果此时最后一步选择了偷i-2而不是i-3，就说明偷i-2一定比偷i-3总钱更多；而
// 如果最后一步偷的仍然是i-3（和只遍历到i-3时一样），那么说明dp[i-2]=dp[i-3]，结合这两种情况，所以不用
// 考虑dp[i-3]。

// 简单一句话就是，往后一步偷到的钱，不可能比往前一步的少，最多也就一样。

class Solution {
public:
    int rob(vector<int>& nums) {
        // n=nums.size()方便后续使用。
        int n = nums.size();
        // 动态规划模板：dp[]用vector定义。
        vector<int> dp(n, 0);

        // 动态规划模板：边界条件考虑，和初始化对齐，否则初始化时，dp[]报错越界。
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        if (n == 3) return max(nums[1], nums[0] + nums[2]);

        // 动态规划模板：dp[]初始化，因为递推公式涉及到i-3，所以初始化0 1 2，否则for循环内报错越界。
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        dp[2] = max(nums[1], nums[0] + nums[2]);

        // 动态规划模板：从i=3遍历到n-1，3个候选值中，取最大的。
        for (int i = 3; i < n; i++) {
            int tmp = max(dp[i - 2] + nums[i], dp[i - 3] + nums[i]);
            dp[i] = max(tmp, dp[i - 1]);
        }

        // 动态规划模板：错误时打印dp[]，带入简单例子进去递推，帮助调试。
        // for (int i = 0; i < n; i++) {
        //     cout<<"i:"<<i<<" dp:"<<dp[i]<<endl;
        // }

        // 动态规划模板：返回dp[]最后一个元素：dp[n-1]。
        return dp[n - 1];
    }
};

动态规划

思路：动态规划的典型例题。这题一看，就应该是贪心算法或动态规划来解，稍加思索后，
发现问题是“一夜能偷到的最高金额”，即“遍历数组后，这一过程收获的最大值”，考虑dp[i]
表示“遍历到i时的收获的最大值”，然后由于“至少要隔一个偷”，这也“很符合状态转移公式”，
因为会涉及到i-1、i-2之类，就自然而然考虑“动态规划”。

动归五部曲：
1：确定dp数组及下标的含义。dp[i]：遍历数组到i时，当前的能获得的最高金额。
2：确定递推公式。dp[i]=max(dp[i-2]+nums[i],dp[i-1])。要么是前一个(和当前值隔开)，要么是前二个+当前值。
3：初始化dp数组。dp[0]=nums[0]、dp[1]=max(nums[0], nums[1])。
注：因为递推公式涉及到dp[n-1]、dp[n-2]，所以要想到初始化dp[1]、dp[0]。
注：由于要初始化dp[1]、dp[0]，所以for()遍历要从i=2开始。而且边界条件if()需要考虑nums[]长度为0和1时
特殊处理，否则访问dp[0]、dp[1]会出错。

注：此外，可见dp[1]=max(nums[0], nums[1])形如这种不确定的值，也是可以当作“初始化”的，因为在递推过程中，
dp[1]的值就会被计算出来，这不是我们需要太过考虑的事情。

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