एल्गोरिदम अपने मूल्य

Question

को अधिकतम करने के लिए अभिव्यक्ति को ब्रैकेट करने के लिए गतिशील प्रोग्रामिंग पर समस्याओं को देखते हुए मुझे यह मिला। आपको फॉर्म V0 O0 V1 O1 की एक अनूठी अभिव्यक्ति दी गई है .... Vn-1

हमें उन स्थानों पर ब्रैकेट रखना होगा जो संपूर्ण अभिव्यक्ति के मूल्य को अधिकतम करते हैं।

वी ऑपरेशंस हैं और ओ ऑपरेटर हैं। समस्या ऑपरेटरों के पहले संस्करण में * और + हो सकता है और ऑपरेटरों सकारात्मक हैं। समस्या का दूसरा संस्करण पूरी तरह से सामान्य है।

पहले संस्करण के लिए मैं डीपी समाधान के साथ आया था।

समाधान - एक [] = ऑपरेंड सरणी बी [] - ऑपरेटरों सरणी टी (ए [i, j]) - अभिव्यक्ति टी की अधिकतम मूल्य (ए [0, n-1]) = अधिकतम से अधिक सब मैं {(टी (ए [0, i]) ओई टी (ए [आई + 1, एन -1]))}

सीमा के मामले छोटे हैं (जब मैं = जे)। मुझे निम्नलिखित के साथ मदद की ज़रूरत है - इस एल्गोरिदम के चलने वाले समय का विश्लेषण करें। और यदि कोई बेहतर है।

Answer 1

छोटे श्रेणी से लेकर लंबी श्रेणियों के A[i,j] तत्वों की गणना का विश्लेषण करना आसान है। उस के लिए एल्गोरिथ्म लगता है कि:

# 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] 

A[] के बाद से लगातार समय एक्सेस (सरणी) एल्गोरिथ्म से साथ लागू किया जा सकता O(n^3) है।