Cướp nhà II trong C++

Giả sử bạn là một tên cướp chuyên nghiệp. Bạn đang lên kế hoạch cướp các ngôi nhà dọc theo một con đường. Mỗi ngôi nhà có một số tiền nhất định. Tất cả các ngôi nhà được sắp xếp thành một vòng tròn. Điều đó 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 ta phải nhớ rằng các ngôi nhà liền kề có hệ thống bảo mật kết nối và sẽ tự động báo cảnh sát nếu hai ngôi nhà liền kề bị đột nhập vào cùng một đêm. Vì vậy, nếu chúng ta có một danh sách số nguyên biểu thị 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 báo động cảnh sát. Vì vậy, nếu mảng là [1,2,3,1], đầu ra sẽ là 4.

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:

• Chúng ta sử dụng một module gọi là solve(), nhận mảng, start và end, hoạt động như sau:
• ans := nums[start]
• Tạo một bảng quy hoạch động, tên là dp, kích thước giống nums.
• dp[start] := nums[start]
• for i := start + 1 đến end
  • last := dp[i – 1]
  • lastToLast := 0 khi i – 2, ngược lại dp[i – 2]
  • dp[i] := max của nums[i] + lastToLast và last
  • ans := max của dp[i] và ans
• trả về ans
• Việc cướp được thực hiện như sau:
  • n := kích thước nums
  • nếu n bằng 0, trả về 0
  • nếu n = 1, trả về nums[0]
  • trả về max của solve(nums, 0, n - 2), solve(nums, 1, n – 1)

Hãy xem 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]

Đầu ra

7