পাইথনে মিনিমাম পাথ সম বের করুন

একটি m x n ম্যাট্রিক্স দেওয়া আছে যাতে নন-নেগেটিভ ইন্টিজার আছে। টপ-লেফ্ট থেকে বটম-রাইট পর্যন্ত এমন একটি পাথ বের করতে হবে যাতে পাথে পড়া সব সংখ্যার যোগফল ন্যূনতম হয়। মুভমেন্ট শুধু ডাউন বা রাইট হতে পারে।

ম্যাট্রিক্স: 1 3 1 1 5 1 4 2 1 আউটপুট 7, পাথ: 1,3,1,1,1।

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

row := রো সংখ্যা, column := কলাম সংখ্যা
i := row-1, j := column-1
লাস্ট রো এবং লাস্ট কলাম প্রিপ্রসেস করুন (কামুলেটিভ সম)
বাকি সেলগুলোতে: matrix[i][j] += min(matrix[i][j+1], matrix[i+1][j])
matrix[0][0] রিটার্ন

উদাহরণ

class Solution(object):
    def minPathSum(self, grid):
        row = len(grid) - 1
        column = len(grid[0]) - 1
        i = row - 1
        j = column - 1
        while j >= 0:
            grid[row][j] += grid[row][j+1]
            j -= 1
        while i >= 0:
            grid[i][column] += grid[i+1][column]
            i -= 1
        j = column - 1
        i = row - 1
        while i >= 0:
            while j >= 0:
                grid[i][j] += min(grid[i][j+1], grid[i+1][j])
                j -= 1
            j = column - 1
            i -= 1
        return grid[0][0]

ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

ইনপুট

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