পাইথনে একটি ম্যাট্রিক্স থেকে সর্বাধিক কয়েন সংগ্রহ করার সমস্যা

ধরুন, আমাদের কাছে একটি ২D ম্যাট্রিক্স আছে যার সেলগুলোতে কয়েনের সংখ্যা দেওয়া আছে। দুজন বন্ধু কয়েন সংগ্রহ করবেন এবং তারা শুরুতে উপরের বাম কোণা (top-left) এবং উপরের ডান কোণা (top-right) থেকে শুরু করবে। তাদের অনুসরণ করতে হবে নিচের নিয়মগুলো:

কোনো সেল (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 ? A[r][c2] : 0)
- base := ans
- প্রতিটি nc1 ∈ {c1-1, c1, c1+1} এবং nc2 ∈ {c2-1, c2, c2+1} এর জন্য:
  - যদি 0 ≤ nc1 < C এবং 0 ≤ nc2 < C হয়, তবে ans := max(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]]