पायथन में खेल में एकत्र किए जा सकने वाले अधिकतम अंक खोजने का प्रोग्राम

मान लीजिए हम कार्ड का खेल खेल रहे हैं। हमें कई कार्ड रैखिक रूप से व्यवस्थित दिए गए हैं जिन पर एक संख्या है। कार्ड पर संख्याएं बेतरतीब ढंग से वितरित हैं; और कार्ड की शुरुआत और अंत में, संख्या 1 वाले दो कार्ड डाले जाते हैं। अब, खेल में, हमें दिए गए कार्डों को उठाकर अधिकतम अंक एकत्र करने हैं। कार्ड सरणी cards में दर्शाए गए हैं जहां सरणी में तत्व cards[i] की संख्या दर्शाते हैं। जब हम कार्ड i उठाते हैं, तो हम cards[i - 1] * cards[i] * cards[i + 1] अंक एकत्र करते हैं। जब हम एक कार्ड उठाते हैं, तो cards[i - 1] और cards[i] पड़ोसी बन जाते हैं। इसलिए, इन दिए गए कार्डों से हम अधिकतम अंक पता लगाते हैं जो हम एकत्र कर सकते हैं।

इसलिए, यदि इनपुट है cards = [7, 5, 9, 10], तो आउटपुट होगा 1025।

इसलिए खेल में, हम उठा सकते हैं:

इंडेक्स 1 पर कार्ड और 7 * 5 * 9 = 315 अंक प्राप्त करें।
नए इंडेक्स 1 पर कार्ड और 7 * 9 * 10 = 630 अंक प्राप्त करें।
इंडेक्स 1 पर कार्ड और 7 * 10 = 70 अंक प्राप्त करें।
अंतिम कार्ड और 10 अंक प्राप्त करें।

कुल अंक = 315 + 630 + 70 + 10 = 1025

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

search() फ़ंक्शन परिभाषित करें। यह x, y लेगा:
- temp := 0
- z के लिए x + 1 से y तक की रेंज में, करें:
  - temp := max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
- temp लौटाएं
मान 1 और 1 को सूची cards की शुरुआत और अंत में क्रमशः डालें
search(0, cards का आकार - 1) लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(cards):
    def search(x, y):
        temp = 0
        for z in range(x + 1, y):
            temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
        return temp
    cards = [1] + cards + [1]
    return search(0, len(cards) - 1)
print(solve([7, 5, 9, 10]))

इनपुट

[7, 5, 9, 10]