Chương trình tìm thời gian tối thiểu để hoàn thành tất cả các tác vụ trong python

Giả sử chúng ta có một danh sách các số được gọi là num trong đó mỗi giá trị xác định một đơn vị thời gian cần để hoàn thành một tác vụ. Chúng tôi có thể bỏ qua bất kỳ nhiệm vụ nào không liên tiếp, chúng tôi phải tìm thời gian tối thiểu để hoàn thành tất cả các nhiệm vụ.

Vì vậy, nếu đầu vào giống như nums =[11, 6, 8, 16], thì đầu ra sẽ là 14, vì chúng ta có thể bỏ qua tác vụ đầu tiên và cuối cùng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• n:=kích thước của nums
• table:=tạo một ma trận n x 2 và điền vào giá trị này bằng 0
• bảng [0, 0]:=0
• bảng [0, 1]:=nums [0]
• đối với tôi trong phạm vi từ 1 đến n - 1, thực hiện
  • table [i, 0]:=table [i - 1, 1]
  • table [i, 1] =(tối thiểu của bảng [i - 1, 0] và table [i - 1] [1]) + nums [i]
• trả về số hàng tối thiểu trong bảng [n - 1]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

class Solution:
   def solve(self, nums):
      n = len(nums)
      table = [[0] * 2 for _ in range(n)]

      table[0][0] = 0
      table[0][1] = nums[0]

      for i in range(1, n):
         table[i][0] = table[i - 1][1]
         table[i][1] = min(table[i - 1][0], table[i - 1][1]) + nums[i]

      return min(table[n - 1])

ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))

Đầu vào

[11, 6, 8, 16]

Đầu ra

14