二叉树的最大路径和
矩阵的最小路径和
http://www.nowcoder.com/questionTerminal/7d21b6be4c6b429bb92d219341c4f8bb
题目描述
给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。
题解
第一行 只能从左往右
第一个元素 的值为 原数组的第一个元素 dp[0][0] = a[0][0]
dp[0][j] = a[0][j] + dp[0][j-1];
第一列元素 只能从上往下
dp[i][0] = dp[i-1][0] + a[i][0]
第二行第二列元素的可能从 当前节点的左节点 和上节点过来
那么该节点的最小值应为 当前节点的值 加上 min ( 上节点 左节点)
dp[i][j] = a[i][j] + Math.min(dp[i][j-1],dp[i-1][j]);
那么最后一个节点的值就为最小的路径和
import java.util.*; public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { int[][] dp = new int[matrix.length][matrix[0].length]; dp[0][0] = matrix[0][0]; for(int i =1; i< matrix.length; i++) { dp[i][0] = dp[i-1][0] + matrix[i][0]; } for(int i =1; i< matrix[0].length; i++) { dp[0][i] = dp[0][i-1] + matrix[0][i]; } for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[0].length; j++) { dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j], dp[i][j-1]); } } return dp[matrix.length-1][matrix[0].length-1]; } }