House Robber-链接
实现的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<iostream>
#include<vector>
#include<cmath>
using namespace std;
class Solution {
public:
int MAX(vector<int>&arr,int n)
{
int max=arr[0];
for(int i=1;i<=n;i++)
{
if(arr[i]>max)
max=arr[i];
}
return max;
}
int rob(vector<int>& nums) {
if(nums.size()==NULL)
return 0;
vector<int>arr(nums.size(),0);
int ans=0;
arr[0]=nums[0];
if(nums.size()>1)
arr[1]=nums[1];
for(int i=2;i<nums.size();i++)
//我们需要在arr数组中找出下标i-2前最大的那个然后再加上nums[i]存入arr[i];
arr[i]=nums[i]+MAX(arr,i-2);
//最后只需要将arr数组中最大的那个元素找出来就是答案了
int max=arr[0];
for(int i=1;i<arr.size();i++)
{
if(arr[i]>max)
max=arr[i];
}
return max;
}
};
int main()
{
vector<int>a={2,7,9,3,1};
cout<<Solution().rob(a)<<endl;
return 0;
}
|
附上AC的参数
这是一道简单的DP，刚开始做的时候还是想了一会，毕竟我很菜……
1.后来发现如果我们只考虑1个房子的话，那小偷没得挑，只得选择这一个房子偷；
2.接着想2个房子的话，小偷会偷2个房子中钱最多的那个(因为不能触发警报只能偷其中的一个);
3.如果是3个房子的话，我们需要先偷第3个房子，然后将从第一个房子开始到第三个房子前面前面的那个房子(这里也就是第一个房子)找出最大的那个，然后将第3个房子的价值与这个最大的价值相加存入arr数组，此时我们得到的偷前3所房子的价值分布
4.如果是4所房子，我们需要先偷第4所房子，然后将第一所房子到第4所前面前面的那个房子的最大值在arr数组中找出来，然后相加。也就是我们需要找max(arr[0],arr[4-2])的最大值然后与第四所房子的值相加，这样我们就得到了偷前4所房子的价值分布
接着我们就以此类推，最后得到我们需要的结果。注意为什么这里是从第一所房子到我们当前偷的这个房子的前面的前面的房子中找寻最大的(因为相邻的房子一旦被偷就会触发警报)
不必纠结，arr数组中存的都是合理的偷房子的价值
说实话，DP很有趣，但是DP很难，要是遇到难一点的DP，一点也不会…
