สมมติว่าเรามีอาร์เรย์ที่เรียกว่าเป้าหมายที่มีค่าบวก ตอนนี้ให้พิจารณาอาร์เรย์เริ่มต้นที่มีขนาดเท่ากันกับศูนย์ทั้งหมด เราต้องหาจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการสร้างอาร์เรย์เป้าหมายจากค่าเริ่มต้นหากเราดำเนินการนี้:(เลือกอาร์เรย์ย่อยใดก็ได้จากค่าเริ่มต้นและเพิ่มแต่ละค่าทีละหนึ่ง)
ดังนั้น ถ้าอินพุตเหมือนเป้าหมาย =[2,3,4,3,2] ผลลัพธ์จะเป็น 4 เพราะอาร์เรย์เริ่มต้นคือ [0,0,0,0,0] ก่อนส่ง select subarray จากดัชนี 0 ถึง 4 และเพิ่ม 1 ดังนั้นอาร์เรย์จะเป็น [1,1,1,1,1] จากนั้นเลือกจากดัชนี 0 ถึง 4 อีกครั้งเพื่อสร้าง [2,2,2,2,2] จากนั้นเลือกองค์ประกอบจาก ดัชนี 1 ถึง 3 และเพิ่มขึ้น ดังนั้นอาร์เรย์จะเป็น [2,3,3,3,2] และสุดท้ายเลือกดัชนี 2 และสร้างอาร์เรย์ [2,3,4,3,2] ซึ่งเหมือนกับเป้าหมาย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
prev_num :=0
-
ขั้นตอน :=0
-
สำหรับแต่ละ val ในเป้าหมาย ให้ทำ
-
steps :=steps + val - prev_num if val> prev_num มิฉะนั้น 0
-
prev_num :=วาล
-
-
กลับขั้นตอน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(target):
prev_num = 0
steps = 0
for val in target:
steps += val-prev_num if val > prev_num else 0
prev_num = val
return steps
target = [2,3,4,3,2]
print(solve(target)) อินพุต
[2,3,4,3,2]
ผลลัพธ์
4
