Chương trình tìm điểm tối đa từ việc thực hiện các phép toán nhân trong Python

Giả sử chúng ta có hai mảng num và cấp số nhân có kích thước lần lượt là n và m (n> =m). Các mảng được lập chỉ mục 1. Bây giờ điểm số ban đầu của chúng tôi là 0. Chúng tôi muốn thực hiện chính xác m phép toán. Trong hoạt động thứ i (được lập chỉ mục 1), chúng tôi sẽ -

Chọn một giá trị từ x từ đầu hoặc cuối các số.
Thêm hệ số [i] * x vào điểm số.
Xóa x khỏi số mảng.

Chúng ta phải tìm điểm tối đa sau khi thực hiện m hoạt động.

Vì vậy, nếu đầu vào giống như nums =[5,10,15], nhân =[5,3,2], thì đầu ra sẽ là 115 vì chúng ta có thể lấy 15 rồi nhân với 5 để được 5 * 15 =75 , thì 10 * 3 =30, do đó tổng là 75 + 30 =105 và cuối cùng là 5 * 2 =10, do đó tổng 105 + 10 =115.

Để 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, m:=kích thước nhân
dp:=Một mảng 2D kích thước m x (m + 1) và điền bằng 0
đối với tôi, ngược lại phạm vi danh sách từ 0 đến m - 1, thực hiện
- đối với j trong phạm vi i đến m - 1, thực hiện
  - k:=i + m - j - 1
  - dp [i, j] =tối đa (nums [i] * nhân [k] + dp [i + 1, j]) và (nums [j-m + n] * nhân [k] + dp [i, j -1])
trả về phần tử cuối cùng của dp [0]

Ví dụ

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

def solve(nums, multipliers):
   n, m = len(nums), len(multipliers)
   dp = [[0]*m for _ in range(m+1)]

   for i in reversed(range(m)):
      for j in range(i, m):
         k = i + m - j - 1
         dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])

   return dp[0][-1]

nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))

Đầu vào

[5,10,15], [5,3,2]

Chương trình tìm điểm tối đa từ việc thực hiện các phép toán nhân trong Python

Ví dụ

Đầu vào

Đầu ra