求解最值问题利用动态规划算法解决

题目描述：给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

示例1：

输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值：12

备注：1≤n,m≤2000

思路分析：

求最值问题首先就是构建辅助数组dp
路径的走向只能是向右或者是向下，则可以将没有元素的对于的和求解出来构建一个新的二维表
二维表中国填写当前值与前一次值之和，取左下右上的两值的最小值与当前值求和填充表格

    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        if(matrix==null)return 0;
		//构建列
		int row = matrix.length;
		int column = matrix[0].length;
		//构建列的值
		for(int i = 1;i<row;i++)matrix[i][0] = matrix[i-1][0]+matrix[i][0];
		//构建行的值
		for(int j = 1;j<column;j++)matrix[0][j] = matrix[0][j-1] + matrix[0][j];
        //填充中间数据
		for(int i = 1;i<row;i++){
 			for(int j=1;j<column;j++)
				matrix[i][j] = Math.min(matrix[i-1][j],matrix[i][j-1]) + matrix[i][j];
		}
		return matrix[row-1][column-1];
	}

这里将dp数组的构建放在了原数组中