C++-এ ম্যাট্রিক্সে মিনিমাম পাথ সম (Minimum Path Sum)

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

উদাহরণ ম্যাট্রিক্স:

সমাধান: ডাইনামিক প্রোগ্রামিং (বটম-আপ)। লাস্ট রো ও লাস্ট কলামে কিউমুলেটিভ সум ক্যালকুলেট করে বাকি সেলগুলোতে মিনিমাম পাথ সুম আপডেট।

উদাহরণ

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])

ইনপুট

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

আউটপুট

7