พิจารณาว่าคุณเป็นโจรมืออาชีพ และคุณกำลังวางแผนที่จะปล้นบ้านตามถนน แต่ละบ้านมีเงินเก็บอยู่จำนวนหนึ่ง บ้านทุกหลังจัดเป็นวงกลม นั่นหมายถึงบ้านหลังแรกเป็นเพื่อนบ้านของบ้านหลังสุดท้าย เราต้องจำไว้ว่าบ้านที่อยู่ติดกันมีระบบรักษาความปลอดภัยเชื่อมต่อและจะติดต่อตำรวจโดยอัตโนมัติหากบ้านสองหลังถูกบุกรุกในคืนเดียวกัน ดังนั้นหากเรามีรายการจำนวนเต็มที่แสดงถึงจำนวนเงินของแต่ละบ้าน ให้กำหนดจำนวนเงินสูงสุดที่คุณสามารถปล้นได้ในคืนเดียวโดยไม่ต้องแจ้งตำรวจ ดังนั้นหากอาร์เรย์คือ [1,2,3,1] ผลลัพธ์จะเป็น 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เรากำลังใช้โมดูลหนึ่งที่เรียกว่า Solve() ซึ่งจะรับอาร์เรย์ จุดเริ่มต้นและจุดสิ้นสุด ซึ่งจะทำหน้าที่ด้านล่าง −
- ans :=nums[start]
- สร้างหนึ่งตารางสำหรับโปรแกรมไดนามิก ชื่อ dp และขนาดเท่ากับขนาด nums
- dp[start] :=nums[start]
- for i :=start + 1 to end
- สุดท้าย :=dp[i – 1]
- lastToLast :=0 เมื่อ i – 2 มิฉะนั้น dp[i – 2]
- dp[i] :=สูงสุดของ nums[i] + lastToLast และล่าสุด
- ans :=สูงสุดของ dp[i] และ ans
- คืนสินค้า
- การปล้นทำได้ดังนี้ -
- n :=ขนาดของ nums
- ถ้า n เป็นศูนย์ ให้คืนค่า 0
- ถ้า n =1 ให้คืนค่า nums[0]
- คืนค่าสูงสุดของการแก้(nums, 0, n - 2), แก้(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
