C ++中的House Robber II

考虑一下，你是一个职业强盗。而且您打算抢劫沿街的房屋。每个房子都有一定量的钱。所有房屋都围成一圈。这意味着第一所房子是最后一所房子的邻居。我们必须记住，相邻的房屋已连接了安全系统，如果在同一晚闯入两所相邻的房屋，它将自动与警察联系。因此，如果我们有一个表示每个房屋的总金额的整数列表，请确定您在一夜内可以抢走的最大金额，而不必通知警察。因此，如果数组为[1,2,3,1]，则输出为4。

为了解决这个问题，我们将遵循以下步骤-

• 我们正在使用一个名为的模块solve()，它将采用数组，开始和结束，其行为如下：

• ans：= nums [开始]

• 创建一个用于动态编程的表，名称为dp，大小与nums大小相同。

• dp [start]：= nums [start]

• 对于我：=开始+1到结束

• 最后：= dp [i – 1]

• 当i – 2时，lastToLast：= 0，否则dp [i – 2]

• dp [i]：= nums [i]的最大值+ lastToLast和last

• ans：= dp [i]和ans的最大值

• 返回ans

• 抢劫完成如下-

• n：= nums的大小

• 如果n为零，则返回0

• 如果n = 1，则返回nums [0]

• 返回最大的solve(nums,0,n-2)，solve(nums,1,n-1)

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector <int>& nums, int start, int end){
      int ans = nums[start];
      vector <int> dp(nums.size());
      dp[start] = nums[start];
      for(int i = start + 1; i <= end; i++){
         int last = dp[i - 1];
         int lastToLast = i - 2 < start? 0 : dp[i - 2];
         dp[i] = max(nums[i] + lastToLast, last);
         ans = max(dp[i], ans);
      }
      return ans;
   }
   int rob(vector<int>& nums) {
      int n = nums.size();
      if(!n)return 0;
      if(n == 1)return nums[0];
      return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
   }
};
main(){
   vector<int> v = {1,2,3,5};
   Solution ob;
   cout << ob.rob(v);
}

输入值

[1,2,3,5]

输出结果

7