Với 2 mảng các số không âm, tìm tổng tối thiểu các sản phẩm

Question

Với hai mảng A và B, mỗi chứa n số không âm, loại bỏ các yếu tố a>0 từ ngày kết thúc của A và b>0 yếu tố từ cuối B. Đánh giá chi phí của một hoạt động như X*Y trong đó X là tổng của các phần tử a bị xóa khỏi các phần tử A và Y tổng các phần tử b bị xóa khỏi B. Tiếp tục làm điều này cho đến khi cả hai mảng trống. Mục đích là để giảm thiểu tổng chi phí.

Sử dụng lập trình động và thực tế là chiến lược tối ưu sẽ luôn lấy chính xác một phần tử từ A hoặc B Tôi có thể tìm thấy giải pháp O (n^3). Bây giờ tôi tò mò muốn biết nếu có một giải pháp thậm chí còn nhanh hơn cho vấn đề này?

EDIT: Trộm cắp một ví dụ từ @recursive trong các ý kiến:

A = [1,9,1] và B = [1, 9, 1]. Có thể làm với chi phí 20. (1) * (1 + 9) + (9 + 1) * (1)

Answer 1

Đây là O(n^2). Gọi CostA(i, j) là chi phí tối thiểu để loại bỏ A[1..i], B[1..j] theo cách mà lần xóa đầu tiên chỉ mất một phần tử từ B. Gọi CostB(i, j) là chi phí tối thiểu để loại bỏ A[1..i], B[1..j] theo cách mà lần xóa đầu tiên chỉ mất một phần tử từ A. Chúng tôi có tái phát lẫn nhau đệ quy

CostA(i, j) = A[i] * B[j] + min(CostA(i - 1, j), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 
CostB(i, j) = A[i] * B[j] + min(CostB(i, j - 1), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 

với trường hợp cơ sở

CostA(0, 0) = 0 
CostA(>0, 0) = infinity 
CostA(0, >0) = infinity 
CostB(0, 0) = 0 
CostB(>0, 0) = infinity 
CostB(0, >0) = infinity. 

Câu trả lời là min(CostA(n, n), CostB(n, n)).