House Robber II trong C ++

Hãy xem xét, bạn là một tên cướp chuyên nghiệp. Và bạn đang có ý định cướp nhà dọc một con phố. Mỗi nhà đều có một số tiền nhất định được cất giữ. Tất cả các ngôi nhà đều được sắp xếp theo hình tròn. Có nghĩa là ngôi nhà đầu tiên là hàng xóm của ngôi nhà cuối cùng. Chúng tôi cần lưu ý rằng các ngôi nhà liền kề có hệ thống an ninh được kết nối và nó sẽ tự động liên lạc với cảnh sát nếu hai ngôi nhà liền kề bị đột nhập trong cùng một đêm. Vì vậy, nếu chúng ta có một danh sách các số nguyên đại diện cho số tiền của mỗi ngôi nhà, hãy xác định số tiền tối đa bạn có thể cướp trong một đêm mà không cần báo cho cảnh sát. Vì vậy, nếu mảng là [1,2,3,1], thì đầu ra sẽ là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Chúng tôi đang sử dụng một mô-đun có tên là giải quyết (), mô-đun này sẽ nhận mảng, bắt đầu và kết thúc, sẽ hoạt động như bên dưới -
ans:=nums [start]
tạo một bảng để lập trình động, tên đó là dp và kích thước giống với kích thước nums.
dp [start]:=nums [start]
for i:=start + 1 to end
- cuối cùng:=dp [i - 1]
- lastToLast:=0 khi i - 2, nếu không thì dp [i - 2]
- dp [i]:=tối đa nums [i] + lastToLast và cuối cùng
- ans:=max of dp [i] và ans
trả lại ans
Cướp được thực hiện như bên dưới -
n:=kích thước của nums
nếu n bằng 0, thì trả về 0
nếu n =1, thì trả về nums [0]
trả về tối đa của giải (nums, 0, n - 2), giải quyết (nums, 1, n - 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

[1,2,3,5]

House Robber II trong C ++

Ví dụ

Đầu vào

Đầu ra