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

मान लीजिए हमारे पास एक 2D मैट्रिक्स है जिसमें सेल्स सिक्कों की संख्या दर्शाते हैं। हमारे दो दोस्त सिक्के एकत्र करने के लिए हैं, और वे शुरुआत में ऊपरी बाएं कोने और ऊपरी दाएं कोने पर रखे गए हैं। वे इन नियमों का पालन करते हैं:

सेल (i, j) से, एक सिक्का-संग्रहकर्ता सेल (i + 1, j - 1), (i + 1, j), या (i + 1, j + 1) पर जा सकता है।
एक सेल पर पहुंचने पर वे उसमें उपलब्ध सभी सिक्के एकत्र कर लेते हैं जिससे वह सेल खाली हो जाता है।
संग्रहकर्ता एक सेल पर रुक सकते हैं, लेकिन किसी भी सेल के सिक्के केवल एक बार एकत्र किए जा सकते हैं।

हमें एकत्र किए जा सकने वाले अधिकतम सिक्कों की संख्या ज्ञात करनी है।

इसलिए, यदि इनपुट इस प्रकार है:

0	4	1	0
3	1	4	0
2	5	1	1
3	0	0	0

तो आउटपुट 17 होगा।

हल करने के चरण

A := इनपुट मैट्रिक्स
R := A की पंक्तियों की संख्या
C := A के स्तंभों की संख्या
एक फ़ंक्शन dp() परिभाषित करें। यह r, c1, c2 लेगा
- यदि r, R के समान है, तो 0 लौटाएं
- ans := A[r, c1] + (यदि c1, c2 के बराबर नहीं है तो 1 अन्यथा 0) * A[r, c2]
- base := ans
- nc1 के लिए [c1 - 1, c1, c1 + 1] में से प्रत्येक के लिए, करें
  - nc2 के लिए [c2 - 1, c2, c2 + 1] में से प्रत्येक के लिए, करें
    - यदि 0 <= nc1 < C और 0 <= nc2 < C, तो
      - ans := ans और (base + dp(r + 1, nc1, nc2)) का अधिकतम
- ans लौटाएं
dp(0, 0, C - 1) लौटाएं

उदाहरण

class Solution:
    def solve(self, A):
        R, C = len(A), len(A[0])
        def dp(r, c1, c2):
            if r == R:
                return 0
            ans = base = A[r][c1] + (c1 != c2) * A[r][c2]
            for nc1 in [c1 - 1, c1, c1 + 1]:
                for nc2 in [c2 - 1, c2, c2 + 1]:
                    if 0 <= nc1 < C and 0 <= nc2 < C:
                        ans = max(ans, base + dp(r + 1, nc1, nc2))
            return ans
        return dp(0, 0, C - 1)

ob = Solution()
print(ob.solve([
    [0, 4, 1, 0],
    [3, 1, 4, 0],
    [2, 5, 1, 1],
    [3, 0, 0, 0]
]))

इनपुट

[
    [0, 4, 1, 0],
    [3, 1, 4, 0],
    [2, 5, 1, 1],
    [3, 0, 0, 0]
]