สมมติว่ามีเมือง และบ้านแต่ละหลังในเมืองมีจำนวนที่แน่นอน โจรคนหนึ่งต้องการปล้นเงินในคืนเดียว เมืองนี้มีระบบรักษาความปลอดภัย 1 ระบบ ราวกับว่าบ้านสองหลังพังติดต่อกันในคืนเดียวกัน จากนั้นจะโทรแจ้งตำรวจโดยอัตโนมัติ ดังนั้นเราต้องค้นหาว่าโจรปล้นได้มากสุดแค่ไหน?
หนึ่งอาร์เรย์มีให้ที่ดัชนี i A[i] คือจำนวนที่มีอยู่ในบ้านที่ i สมมติว่าอาร์เรย์มีลักษณะดังนี้:A =[2, 7, 10, 3, 1] ผลลัพธ์จะเป็น 13 ค่าสูงสุดคือเอาจาก house1 (ค่า 2) จาก house3 (ค่า 10) และ house5 (ค่า 1 ) ดังนั้นทั้งหมดคือ 13
เพื่อแก้ปัญหานี้ เราจะปฏิบัติตามแนวทางนี้ -
- ใช้ prev1 :=0 และ prev2 =0
- สำหรับ i =0 ถึงความยาวของ A −
- อุณหภูมิ :=ก่อนหน้า 1
- prev1 :=สูงสุดของ prev2 + A[i] และ prev1
- prev2 =อุณหภูมิ
- ย้อนกลับก่อนหน้า1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
คลาส Solution(object):def rob(self, nums):""" :type nums:List[int] :rtype:int """ prev2 =0 prev1 =0 for i in range(0,len( nums)):temp =prev1 prev1 =max(prev2+nums[i],prev1) prev2 =temp return prev1ob1 =Solution()print(ob1.rob([2,7,10,3,1]))อินพุต
nums =[2,7,10,3,1]ผลลัพธ์
13
