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

मान लीजिए, हमारे पास एक 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 होगा।

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

ए:=इनपुट मैट्रिक्स
आर:=ए की पंक्ति गणना
सी:=ए की कॉलम संख्या
एक फ़ंक्शन को परिभाषित करें dp() । इसमें r, c1, c2
. लगेगा
- यदि r, R के समान है, तो
  - वापसी 0
- उत्तर:=ए [आर, सी 1] + (यदि सी 1 सी 2 के बराबर नहीं है, तो 1 अन्य 0) * ए [आर, सी 2]
- आधार:=उत्तर
- [c1 - 1, c1, c1 + 1] में प्रत्येक nc1 के लिए, करें
  - [c2 - 1, c2, c2 + 1] में प्रत्येक nc2 के लिए, करें
    - अगर 0 <=एनसी1 <सी और 0 <=एनसी2 <सी, तो
      - उत्तर:=अधिकतम उत्तर और (आधार + डीपी (आर + 1, एनसी1, एनसी 2))
- वापसी उत्तर
वापसी डीपी(0, 0, सी -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]
]