পাইথনে ২ডি ম্যাট্রিক্সে ডান ও নিচে চলা সীমাবদ্ধ রেখে সর্বোচ্চ কয়েন সংগ্রহ করার প্রোগ্রাম

মনে করুন একটি ২ডি ম্যাট্রিক্স আছে যেখানে প্রতিটি সেলে কিছু কয়েন আছে। [0,0] থেকে শুরু করে শুধু ডান বা নিচে যেতে পারলে নিচের ডান কোণায় পৌঁছাতে সর্বোচ্চ কয়েন সংগ্রহ করতে হবে।

উদাহরণস্বরূপ, ম্যাট্রিক্স [[1,4,2,2],[6,0,0,5]] হলে আউটপুট ১৪ (পথ: ১,৪,২,২,৫)।

সমাধানের ধাপসমূহ

r = 1 থেকে সারি সংখ্যা পর্যন্ত, A[r][0] += A[r-1][0]
c = 1 থেকে কলাম সংখ্যা পর্যন্ত, A[0][c] += A[0][c-1]
r = 1 থেকে সারি সংখ্যা, c = 1 থেকে কলাম সংখ্যা পর্যন্ত, A[r][c] += max(A[r-1][c], A[r][c-1])
A[-1][-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]]