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.
一刷
题解：
类似于Dijkstra's algorithm, 创建新的矩阵(或者in-place)，每个grid内存有到该点最小sum
Time Complexity - O(mn)， Space Complexity - O(1)。
public class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(i == 0 && j==0) dp[i][j] = grid[i][j];
else if(i==0) dp[i][j] = dp[i][j-1] + grid[i][j];
else if(j == 0) dp[i][j] = dp[i-1][j] + grid[i][j];
else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[n-1][m-1];
}
}
还有一个滚动数组的思路，留到二刷
