要求

• 你是一个小偷，每个房子中有价值不同的宝物，但若偷连续的两栋房子，就会触发报警系统，求最多可偷价值多少的宝物

示例

• [3,4,1,2]，返回6[3,(4),1,(2)]
• [4,3,1,2]，返回6[(4),3,1,(2)]

实现

• 暴力解法：检查所有房子的组合，对每个组合检查是否有相邻房子，若没有则记录其价值，找最大值（(2^n)*n）
• 递归

• 记忆化搜索

1 class Solution {
2 private:
3 // memo[i] 表示抢劫nums[i…n)所能获得的最大收益
4 vector memo;
5 // 考虑抢劫 nums[index…nums.size())范围内房子
6 int tryRob(vector &nums, int index){
7
8 if(index >= nums.size())
9 return 0;
10
11 if( memo[index] != -1 )
12 return memo[index];
13
14 int res = 0 ;
15 for( int i = index ; i < nums.size() ; i ++ ) 16 res = max( res, nums[i] + tryRob(nums, i + 2) ); 17 memo[index] = res; 18 return res; 19 } 20 public: 21 int rob(vector& nums) {
22 memo = vector(nums.size(),-1);
23 return tryRob(nums, 0);
24 }
25 };

• 动态规划

  • 状态转移（n^2）
  • v(n)：偷取标号n的房子
  • 状态 f(n)：偷取[x…n-1]范围内的房子（做什么）
  • 状态转移：f(0) = max { v(0) + f(2) , v(1) + f(3) , v(2) + f(4) , … , v(n-3) + f(n-1) , v(n-2) , v(n-1) }（怎么做）
  • 7-8：判断传入是否为空数组，否则12会越界
  • 16：判断 j+2 是否越界

1 class Solution {
2
3 public:
4 int rob(vector& nums) {
5
6 int n = nums.size();
7 if( n == 0 )
8 return 0;
9
10 // memo[i] 表示抢劫nums[i…n-1]所能获得的最大收益
11 vector memo(n,-1);
12 memo[n-1] = nums[n-1];
13 for( int i = n-2 ; i >= 0 ; i -- )
14 // memo[i]
15 for( int j = i ; j < n ; j ++ )
16 memo[i] = max( memo[i], nums[j] + (j+2 <n ? memo[j+2] : 0 ));
17
18 return memo[0];
19 }
20 };

相关

• 213 House Robber II
• 337 House Robber III
• 309 Best Time to Buy and Sell Stock with Cooldown