【原题】 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.
【解释】 有一个mxn的数组,要求找到从左上到右下的最小的和为多少?
【思路】 基本思路和这题一样
public class Solution {
public int minPathSum(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int[][] dp=new int[m][n];
dp[0][0]=grid[0][0];
int sum=grid[0][0];
for(int i=1;i<m;i++){
sum+=grid[i][0];
dp[i][0]+=sum;
}
sum=grid[0][0];
for(int j=1;j<n;j++){
sum+=grid[0][j];
dp[0][j]=sum;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=Math.min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j]);
}
}
return dp[m-1][n-1];
}
}
若可以更改原数组则可以将空间复杂度降为O(1),见这里。