leetcode-198-House Robber（动态规划）

题目描述：

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).

             Total amount you can rob = 2 + 9 + 1 = 12.

要完成的函数：

int rob(vector<int> &num)

说明：

1、给定一个vector，要求从vector中选出几个数，这几个数不能是彼此相邻的。在这个条件下，挑选出几个数让他们的和达到最大，输出最大的这个和。

2、这道题很明显是动态规划的题目，我们只需要遍历一遍vector就可以得到答案。

动态规划的题目最重要的是要把给定的vector切分成一个又一个的阶段，比如[1,3,1,3,100,3,1]。我们可以这样想：

要达到最大和，我们可以求出前五个数的最大和+1，或者是前四个数的最大和+3/+1,

而前五个数的最大和是前三个数的最大和+100，或者是前两个数的最大和+3/+100.

那看来我们需要把每个数作为一个阶段，求出每个阶段的最大和。

显而易见，如果没有元素，那么最大和为0

如果只有一个元素，那么最大和为第一个元素的值

如果有两个元素，那么最大和为两个元素的max

我们如下构造代码：（附详解）

    int rob(vector<int>& nums)

    {

        int s1=nums.size();

        if(s1==0)//边界条件

            return 0;

        else if(s1==1)//边界条件

            return nums[0];

        else if(s1==2)//边界条件

            return max(nums[0],nums[1]);

        int qian=max(nums[0]+nums[2],nums[1]),hou=max(nums[0],nums[1]),i=4;//把第三个元素这个阶段的最大和叫做qian，
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//把第二个元素这个阶段的最大和叫做hou

        while(i<=s1-1)//开始迭代处理

        {

            hou=max(hou+nums[i-1],qian);//第四个元素这个阶段的最大和，有可能是hou这个阶段的最大和+当前值，也有可能是qian这个阶段的最大和

            qian=max(hou,qian+nums[i]);//第五个元素这个阶段的最大和，有可能是前面hou这个阶段的最大和，也有可能是之前的qian+当前值

            i+=2;//每一步处理完加上2，迭代处理

        }

        if(i==s1)//如果处理完之后还剩最后一个元素没有处理，那么再相同方法处理一下hou的值

            hou=max(hou+nums[i-1],qian);

        return max(qian,hou);

    }

上述代码实测4ms，beats 14.42% of cpp submissions。不知道怎么改进可以更加优化了……

知道的朋友在评论区分享一下呗~~

巴特西

leetcode-198-House Robber（动态规划）

题目描述：

要完成的函数：

说明：

最新文章

热门文章