Thuật toán để định khung một biểu thức để tối đa hóa giá trị của nó

Question

Tôi đã tìm thấy điều này trong khi tìm kiếm các vấn đề về lập trình động. Bạn được cung cấp một biểu thức không bị phân biệt của biểu mẫu V0 O0 V1 O1 .... Vn-1

Chúng ta phải đặt dấu ngoặc tại những vị trí tối đa hóa giá trị của toàn bộ biểu thức.

V là các toán hạng và O là các toán tử. Trong phiên bản đầu tiên của toán tử vấn đề có thể là * và + và toán hạng là dương. Phiên bản thứ hai của vấn đề là hoàn toàn chung chung.

Đối với phiên bản đầu tiên, tôi đã đưa ra giải pháp DP.

Solution - A [] = toán hạng mảng B [] - nhà khai thác mảng T (A [i, j]) - giá trị tối đa của biểu T (A [0, n-1]) = max trên tất cả i {(T (A [0, i]) Oi T (A [i + 1, n-1])}

Các trường hợp biên là tầm thường (khi i = j). Tôi cần trợ giúp với các điều sau - Phân tích thời gian chạy của thuật toán này. Và nếu có tồn tại tốt hơn.

Answer 1

Sẽ dễ dàng hơn khi phân tích tính toán của các yếu tố A[i,j] từ phạm vi ngắn hơn đến phạm vi dài hơn. Thuật toán cho trông giống như:

# Initialization of single values 
for i in 0, ..., n-1: 
    A[i,i] = V[i] 

# Iterate through number of operation 
for d in 1, ..., n-1: 
    # Range start 
    for i in 0, ..., n-1-d: 
    j = i + d 
    A[i,j] = max(A[i,x] O_x A[x+1,j] for x in i, ..., j-1) 

print 'Result', A[0,n-1] 

Kể từ A[] có thể được thực hiện với thời gian truy cập thường xuyên (mảng) so với thuật toán là O(n^3).