Leetcode Minimum Path Sum problem solution YASH PAL, 31 July 2024 In this Leetcode Minimum Path Sum problem solution we have Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Problem solution in Python. class Solution: def minPathSum(self, a: List[List[int]]) -> int: if len(a)==0: return 0 m=len(a) n=len(a[0]) c=[[0 for i in range(n)]for j in range(m)] c[0][0] = a[0][0] for i in range(1, n): c[0][i] = a[0][i]+c[0][i-1] for i in range(1, m): c[i][0] = a[i][0]+c[i-1][0] for i in range(1,m): for j in range(1,n): c[i][j] = min(c[i-1][j], c[i][j-1]) + a[i][j] return c[m-1][n-1] Problem solution in Java. import java.lang.Math; class Solution { public int minPathSum(int[][] grid) { int[][] dpStart = new int[grid.length + 1][grid[0].length + 1]; return dummySoln(dpStart,grid,grid[0].length-1, grid.length-1); } public int dummySoln(int[][] dp,int[][] grid, int x, int y) { if(dp[y][x] != 0){return dp[y][x];} if(x == y && x == 0) { return grid[0][0]; } int totalSum = grid[y][x]; int totalSumLeft = -1; int totalSumUp = -1; if(x-1 >= 0) { totalSumLeft = totalSum + dummySoln(dp, grid, x - 1, y); } if(y-1 >= 0) { totalSumUp = totalSum + dummySoln(dp, grid, x, y-1); } if(totalSumLeft == -1 && totalSumUp != -1) { return totalSumUp; } if(totalSumLeft != -1 && totalSumUp == -1) { return totalSumLeft; } dp[y][x] = Math.min(totalSumLeft, totalSumUp); return Math.min(totalSumLeft, totalSumUp); } } Problem solution in C++. class Solution { public: int minPathSum(vector<vector<int>>& grid) { if (grid.empty()) return 0; int n = grid.size(); int m = grid[0].size(); vector<vector<long long int>> res(n, vector<long long int>(m, 0)); res[0][0] = grid[0][0]; for(size_t i = 1; i < n; i++){ res[i][0] = res[i-1][0]+ grid[i][0]; } for(size_t i = 1; i < m; i++){ res[0][i] = res[0][i-1]+ grid[0][i]; } for(size_t i = 1; i < n; i++){ for(size_t j = 1; j < m; j++){ res[i][j] = min(res[i-1][j] + grid[i][j], res[i][j-1] + grid[i][j]); } } return res[n-1][m-1]; } }; Problem solution in C. int min(int a,int b){ if(a<b) return a; return b; } int minPathSum(int** grid, int gridSize, int* gridColSize){ int m=gridSize,n=gridColSize[0]; if(m==1 && n==1) return grid[0][0]; if(m==1){ int minn=0; for(int j=0;j<n;j++) minn+=grid[0][j]; return minn; } else{ int arr[m][n]; arr[0][0]=grid[0][0]; for(int j=0;j<n;j++){ for(int i=0;i<m;i++){ if(i==0 && j==0) continue; else if(i==0){ arr[i][j]=grid[i][j]+arr[i][j-1]; } else if(j==0) arr[i][0]=grid[i][0]+arr[i-1][j]; else if(i>0 && i<m){ arr[i][j]=grid[i][j]+min(arr[i][j-1],arr[i-1][j]); } } } return arr[m-1][n-1]; } } coding problems