LeetCode 198

待我称王封你为后i 2021-10-30 01:22 196阅读 0赞

问题描述：

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

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

示例 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.最后一步走2级台阶，也就是从8级到10级

2.最后一步走1级台阶，也就是从9级到10级

**那么在上面的基础上假设1级到8级有X种走法，1级到9级有Y种走法，那么1级到10级有几种走法？**

实际上，10级台阶的所有走法可以根据最后一步的不同分为两个部分。

第一部分：最后一步从9级到10级，这种走法的数量和1级到9级的数量一致，也就是Y种。

第二部分：最后一步从8级到10级，这种走法的数量和1级到8级的数量一致，也就是X种。

则f（10）=f（9）+f（8）

依次回推即可，

**在回到本问题，小偷要偷取最大金额，n栋房子最大金额为F(n)可以分解为f（n）= max（f（n-1），f(n-2)+nums\[n\]）;**

**下面看官方解答，**

类似于将premax和currmax都初始化为0，f（-1）=f（0）=0

class Solution {
    public:
        int rob(vector<int>& nums) {
            int prevMax = 0;
            int currMax = 0;
            for (int i=0;i<nums.size();i++) 
            {
                int temp = currMax;
                currMax = max(prevMax + nums[i], currMax);
                prevMax = temp;
            }
            return currMax;
        }
    };

还有一种解法可能理解起来更加明白

int rob(vector<int>& nums) 
    {
    	int sumOdd = 0;
    	int sumEven = 0;
    
    	for (int i = 0; i < nums.size(); i++)
    	{
    		if (i % 2 == 0)
    		{
    			sumEven += nums[i];
    			sumEven = max(sumOdd, sumEven);
    		}
    		else
    		{
    			sumOdd += nums[i];
    			sumOdd = max(sumOdd, sumEven);
    		}
    	}
    	return max(sumOdd, sumEven);
    }

取奇偶相加，让后取最大值