गिनती संख्या। स्ट्रिंग्स

Question

इस प्रश्न को हमारे प्लेसमेंट में किसी कंपनी के कोडिंग राउंड में पूछा गया था।

1 से 9 तक की संख्या वाली स्ट्रिंग को देखते हुए हमें स्ट्रिंग को व्यवस्थित करना होगा जैसे कि यह समूहों में बांटा गया हो। हमें नंबर गिनने की जरूरत है। संभावित स्ट्रिंग्स जैसे कि समूह < = लगातार समूह के योग का योग।

example1
इनपुट: 1234
उत्पादन: 6
स्ट्रिंग्स हैं:

• {1,2,3,4}
• {1,2,34}
• {12 , 3,4}
• {12,34}
• {1,234}
• {1234}

यहाँ पहली संयोजन, 1 4. दूसरे संयोजन, 1 (3 + 4)। और इसी तरह।

Example2
इनपुट: 516
उत्पादन: 3
स्ट्रिंग्स हैं:

• {5,16}
• {51,6}
• {516}

अब सभी तारों को उत्पन्न करने के लिए ब्रूट फोर्स तरीके से लिया गया समय ओ (2^(एन -1)) है। मेरा सवाल है कि इसे बलपूर्वक बल के तरीके से बेहतर तरीके से कैसे हल किया जाए?

बाधा: इनपुट स्ट्रिंग लंबाई 1 < = n < = 1000

Answer 1

यह समस्या कुशलतापूर्वक Dynamic Programming का उपयोग कर हल किया जा सकता। मैंने इसे dp नामक दो आयामी सरणी का उपयोग करके हल किया। वैध विभाजन की संख्या को खोजने के लिए जहां end वें वर्ण अंतिम है और अंतिम स्ट्रिंग start वें वर्ण से शुरू होती है, हमें start-1 वें चरित्र पर समाप्त होने वाले वैध विभाजन की संख्या के लिए पहले गणना और कैश किए गए मान का उपयोग करने की आवश्यकता है। यह संख्या dp[prev_start][start - 1] में सभी कैश किए गए मानों का योग है, जहां prev_start[0, start) के बीच कोई मान हो सकता है, जैसे s[prev_start:start-1] में तत्वों का योग s[start:end] में तत्वों की योग से अधिक नहीं है।

def get_count(s): 
    N = len(s) 
    # Initialize memoization matrix 
    # First row all ones, all others zeros 
    dp = list() 
    dp.append([1] * N) 
    for i in range(N - 1): 
     dp.append([0] * N) 

    # Convert characters to integers 
    s = [ord(i) - ord('0') for i in s] 

    for start in range(1, N): 
     for end in range(start, N): 
      for prev_start in range(0, start): 
       if sum(s[prev_start:start]) <= sum(s[start:end+1]): 
        dp[start][end] += dp[prev_start][start - 1] 

    return sum([dp[i][N - 1] for i in range(N)]) 

print(get_count('516')) 

नोट:: यहाँ Python3 में एक समाधान है समय जटिलता O (n^4) है, लेकिन आप आसानी O (n^3) के लिए अनुकूलित कर सकते हैं।