Minimum Path Sum - Array - Medium - LeetCode

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.

Note: You can only move either down or right at any point in time.

Example:

Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.

public class Solution {
 public int MinPathSum(int[][] grid) {
 int r = grid.Length;
 int c = grid[0].Length;
 var T = new int[r,c];
 for(int i=0;i<r;i++){
 if(i==0){
 T[i,0]=grid[i][0];
 }
 else{
 T[i,0]=grid[i][0] + T[i-1,0]; 
 } 
 }
 
 for(int i=0;i<c;i++){
 if(i==0){
 T[0,i] = grid[0][i];
 }
 else{
 T[0,i] = grid[0][i] + T[0,i-1];
 }
 }
 
 for(int i=1;i<r;i++){
 for(int j=1;j<c;j++){
 T[i,j] = Math.Min(T[i-1,j],T[i,j-1]) + grid[i][j];
 }
 }
 
 return T[r-1,c-1];
 }
}

Time Complexity: O(n^2)

Space Complexity: O(n^2)