สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums ตอนนี้ ให้เราพิจารณาการดำเนินการที่เรานำค่าสองค่าที่ต่อเนื่องกันมารวมกันเป็นค่าเดียวโดยการหาผลรวม เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นเพื่อให้รายการไม่เพิ่มขึ้น
ดังนั้นหากอินพุตเป็นเหมือน nums =[2, 6, 4, 10, 2] ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถรวม [2, 6] เข้าด้วยกันเพื่อรับ [8, 4, 10, 2] แล้ว ผสาน [8, 4] เพื่อรับ [12, 10, 2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้าตัวเลขว่างก็
-
คืนค่า 0
-
-
ใส่ −inf ต่อท้าย nums
-
N :=ขนาดของ nums
-
dp :=รายการขนาด N และเติมด้วย 0
-
arr :=รายการขนาด N และเติมด้วย 0
-
p :=ขนาดของ arr
-
arr[p−1] :=nums[N−1]
-
arr[p−2] :=nums[N−2]
-
สำหรับฉันในช่วง N - 3 ถึง 0 ลดลง 1 ทำ
-
เจ :=ฉัน
-
x :=nums[j]
-
ในขณะที่ j
-
เจ :=เจ + 1
-
x :=x + nums[j]
-
-
dp[i] :=j − i + dp[j + 1]
-
arr[i] :=x
-
-
กลับ dp[0]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, nums):
if not nums:
return 0
nums.append(float("−inf"))
N = len(nums)
dp = [0] * N
arr = [0] * N
arr[−1] = nums[−1]
arr[−2] = nums[−2]
for i in range(N − 3, −1, −1):
j = i
x = nums[j]
while j < N − 1 and x < arr[j + 1]:
j += 1
x += nums[j]
dp[i] = j − i + dp[j + 1]
arr[i] = x
return dp[0]
ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums)) อินพุต
[2, 6, 4, 10, 2]
ผลลัพธ์
2
