题解 | #矩阵的最小路径和#

递归

1.首先新建一个同大小的数组用于存储到达该位置的最短路径。

2. a. 到达（0）（0）位置，需要的最短路径即对应原矩阵的值，

   b.到达第0列上的元素只能通过上面元素这一条路径

   c.到达第0行的元素只能经过其左边的元素这一条路径

   d.其他情况既可以从上面到达也可以从其左侧到达。

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
            // write code here
            int m = matrix.length;
            int n = matrix[0].length;
            int[][] curPath = new int[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(i==0&&j==0){
                        curPath[i][j] = matrix[0][0];
                    }else if(i==0){
                        curPath[i][j] = curPath[i][j-1]+matrix[i][j];
                    }else if(j==0){
                        curPath[i][j] = curPath[i-1][j]+matrix[i][j];
                    }else {
                        curPath[i][j] = Math.min(curPath[i - 1][j] + matrix[i][j], curPath[i][j - 1] + matrix[i][j]);
                    }
                }
            }
            return curPath[m-1][n-1];
        }
}