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)