Giả sử có một thành phố, và mỗi ngôi nhà trong thành phố có một số tiền nhất định. Một tên cướp muốn cướp tiền chỉ trong một đêm. Thành phố có một hệ thống an ninh, đó là nếu hai ngôi nhà liên tiếp bị phá trong cùng một đêm, thì nó sẽ tự động gọi cảnh sát. Vậy chúng ta phải tìm ra số tiền tối đa mà tên cướp có thể cướp được là bao nhiêu?
Một mảng được cung cấp, tại chỉ số i, A [i] là số lượng có trong nhà thứ i. Giả sử mảng như sau:A =[2, 7, 10, 3, 1], thì kết quả sẽ là 13. Tối đa là lấy từ house1 (giá trị 2), từ house3 (giá trị 10) và house5 (giá trị 1 ), vì vậy tổng số là 13
Để giải quyết vấn đề này, chúng tôi sẽ thực hiện theo cách tiếp cận này -
- chiếm trước 1:=0 và trước 2 =0
- cho i =0 đến độ dài của A -
- tạm thời:=trước1
- trước đó 1:=tối đa trước 2 + A [i] và trước 1
- prev2 =temp
- trả lại trước 1
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
class Giải pháp (đối tượng):def rob (self, nums):"" ":type nums:List [int]:rtype:int" "" prev2 =0 prev1 =0 for i in range (0, len ( nums)):temp =prev1 pres1 =max (pres2 + nums [i], prev1) prev2 =temp return prev1ob1 =Lời giải () print (ob1.rob ([2,7,10,3,1]))Đầu vào
nums =[2,7,10,3,1]Đầu ra
13