数字三角形的最短路径

107 阅读 0 评论 71 点赞

我是靠谱客的博主害怕帅哥，这篇文章主要介绍数字三角形的最短路径，现在分享给大家，希望可以做个参考。

 
 描述 

给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

 
 样例 

比如，给出下列数字三角形：
复制代码[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
思路:大家不要被这个样例所迷惑，这个题目的用意不是找每行的最小值，而是去找最短路径，所以数不能跨越两个数来比较。
就是把数组中数两两比较，去最小的值与上一层的父节点相加，这样循环，最后最短路径和即为根节点。
复制代码 public int minimumTotal(int[][] triangle) {
        int len = triangle.length;
        for (int i = len - 2; i >= 0; i--) {
            int len1 = triangle[i].length;
            for (int j = 0; j < len1; j++) {
                triangle[i][j] = triangle[i][j]+Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }


        return triangle[0][0];
    } public int minimumTotal(int[][] triangle) {
        int len = triangle.length;
        for (int i = len - 2; i >= 0; i--) {
            int len1 = triangle[i].length;
            for (int j = 0; j < len1; j++) {
                triangle[i][j] = triangle[i][j]+Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }


        return triangle[0][0];
    }