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

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

उदाहरण के लिए, यदि इनपुट है:

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

• r को 1 से A की पंक्ति संख्या तक के लिए करें:
  • A[r][0] := A[r][0] + A[r-1][0]
• c को 1 से A[0] की स्तंभ संख्या तक के लिए करें:
  • A[0][c] := A[0][c] + A[0][c-1]
  • r को 1 से A के आकार तक के लिए करें:
    • c को 1 से A[0] के आकार तक के लिए करें:
      • A[r][c] = A[r][c] + max(A[r-1][c], A[r][c-1])
• A के नीचे-दाएं कोने का मान वापस करें

उदाहरण

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