पायथन में हम जितने सिक्के एकत्र कर सकते हैं, उन्हें खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक 2D मैट्रिक्स है जहां प्रत्येक सेल कुछ सिक्के संग्रहीत करता है। अगर हम [0,0] से शुरू करते हैं, और केवल दाएं या नीचे जा सकते हैं, तो हमें नीचे दाएं कोने से अधिकतम सिक्कों की संख्या का पता लगाना होगा।

तो, अगर इनपुट पसंद है

तब आउटपुट 14 होगा, जैसा कि हम रास्ता अपनाते हैं:[1, 4, 2, 2, 5]

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

• श्रेणी 1 में r के लिए A की पंक्ति गणना के लिए, करें

  • ए[आर, 0] :=ए[आर, 0] + ए[आर-1, 0]

• सी के लिए श्रेणी 1 में ए की कॉलम गणना के लिए, करें

  • ए[0, सी] :=ए[0, सी] + ए[0, सी-1]

  • r श्रेणी 1 से A के आकार के लिए, करें

  • सी के लिए 1 से लेकर A[0] के आकार तक, करें

  • A[r, c] =A[r, c] + अधिकतम (A[r-1, c] और A[r, c-1]

• ए के निचले दाएं कोने का वापसी मूल्य

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

उदाहरण

class Solution:
   def solve(self, A):
      for r in range(1, len(A)):
         A[r][0] += A[r-1][0]
      for c in range(1, len(A[0])):
         A[0][c] += A[0][c-1]
      for r in range(1, len(A)):
         for c in range(1, len(A[0])):
            A[r][c] += max(A[r-1][c], A[r][c-1])
      return A[-1][-1]
ob = Solution()
matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ]
print(ob.solve(matrix))

इनपुट

matrix = [
   [1, 4, 2, 2],
   [6, 0, 0, 5]
]

आउटपुट

14