House Robber II ใน C++

พิจารณาว่าคุณเป็นขโมยมืออาชีพ และคุณวางแผนจะขโมยบ้านตามถนน แต่ละบ้านมีเงินจำนวนหนึ่งเก็บไว้ บ้านทั้งหมดจัดเรียงในวงกลม หมายความว่าบ้านแรกคือเพื่อนบ้านของบ้านสุดท้าย เราต้องจำไว้ว่าบ้านที่ติดกันมีระบบความปลอดภัยเชื่อมต่อ และจะติดต่อตำรวจโดยอัตโนมัติถ้าบ้านที่ติดกันถูกบุกในคืนเดียวกัน ดังนั้นถ้าเรามีรายการจำนวนเต็มที่แทนจำนวนเงินของแต่ละบ้าน ให้กำหนดจำนวนเงินสูงสุดที่คุณสามารถขโมยได้ในคืนเดียวโดยไม่ทำให้สายรบกวน ดังนั้นถ้าอาร์เรย์คือ [1,2,3,1] ผลลัพธ์จะเป็น 4

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เราใช้โมดูลหนึ่งชื่อ solve() ที่จะรับอาร์เรย์ start และ end ที่จะทำงานดังนี้ -
• ans := nums[start]
• สร้างตารางสำหรับ Dynamic Programming ชื่อ dp และขนาดเท่ากับขนาด nums
• dp[start] := nums[start]
• for i := start + 1 ถึง end
  • last := dp[i - 1]
  • lastToLast := 0 เมื่อ i - 2 มิฉะนั้น dp[i - 2]
  • dp[i] := สูงสุดของ nums[i] + lastToLast และ last
  • ans := max ของ dp[i] และ ans
• return ans
• การขโมยทำดังนี้ -
• n := ขนาดของ nums
• ถ้า n เป็นศูนย์ คืนค่า 0
• ถ้า n = 1 คืนค่า nums[0]
• return สูงสุดของ 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