经典动态规划法。
如果给定矩阵如下：
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
路径1,3,1,0,6,1,0是所有路径中路径和的最小的，1+3+1+0+6+1+0=12，所以返回12。
代码如下：
public class demo5 {
public static void main(String[] args) {
int[][] array = {{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
int[][] result = minPathSum(array);
System.out.println(result[result.length-1][result[0].length-1]);
}
public static int[][] minPathSum(int[][] array) {
int row = array.length;
int col = array[0].length;
int[][] m = new int[row][col];
m[0][0] = array[0][0];
for(int i = 1; i < row; ++i){
m[i][0] = array[i][0] + m[i-1][0];
}
for(int j = 1; j < col; ++j){
m[0][j] = array[0][j] + m[0][j-1];
}
for(int k = 1; k < row; ++k){
for(int kk = 1; kk < col; ++kk){
m[k][kk]= Math.min(m[k-1][kk], m[k][kk-1]) + array[k][kk];
}
}
return m;
}
}