Chương trình tìm số gia số tối thiểu trên các mảng con để tạo thành một mảng mục tiêu trong Python

Giả sử chúng ta có một mảng được gọi là đích với các giá trị dương. Bây giờ hãy xem xét một mảng ban đầu có cùng kích thước với tất cả các số không. Chúng ta phải tìm số lượng thao tác tối thiểu cần thiết để tạo một mảng mục tiêu từ ban đầu nếu chúng ta thực hiện thao tác này:(Chọn bất kỳ mảng con nào từ ban đầu và tăng từng giá trị một.)

Vì vậy, nếu đầu vào là target =[2,3,4,3,2], thì đầu ra sẽ là 4 bởi vì mảng ban đầu là [0,0,0,0,0] trước tiên chuyển chọn mảng con từ chỉ số 0 đến 4 và tăng nó lên 1, vì vậy mảng sẽ là [1,1,1,1,1], sau đó chọn lại từ chỉ số 0 đến 4 để biến nó thành [2,2,2,2,2], sau đó chọn các phần tử từ chỉ số 1 đến 3 và tăng lên, vì vậy mảng sẽ là [2,3,3,3,2], và cuối cùng chọn chỉ số 2 và tạo mảng [2,3,4,3,2] giống với mục tiêu.

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

• trước_num:=0

• bước:=0

• đối với mỗi giá trị trong mục tiêu, hãy thực hiện

  • bước:=bước + val - trước_num nếu val> trước_num nếu không thì 0

  • trước_num:=val

• quay lại các bước

Ví dụ

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

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))

Đầu vào

[2,3,4,3,2]

Đầu ra

4