Leetcode刷题java之120. 三角形最小路径和

逃离我推掉我的手 2023-07-02 09:25 3阅读 0赞

执行结果：

通过

显示详情

执行用时 :3 ms, 在所有 Java 提交中击败了83.94% 的用户

内存消耗 :37.2 MB, 在所有 Java 提交中击败了72.94%的用户

题目：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

\[  
\[2\],  
\[3,4\],  
\[6,5,7\],  
\[4,1,8,3\]  
\]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/triangle  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

自底向上，不断更新最小的值，一直推到最后，计算的递推公式，dp\[i\]\[j\] = min(dp\[i+1\]\[j\], dp\[i+1\[j+1\]) + triangle\[i\]\[j\];

二维的浪费空间，我们可以将其修改为一维的形式。

代码：二维

class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int row=triangle.size();
            int[][] result=new int[row+1][row+1];
            for(int i=row-1;i>=0;i--)
            {
                for(int j=0;j<=i;j++)
                {
                    if(i==row-1)
                    {
                        result[i][j]=triangle.get(i).get(j);
                    }else
                    {
                        result[i][j]=Math.min(result[i+1][j],result[i+1][j+1])+triangle.get(i).get(j);
                    }
                }
            }
            return result[0][0];
        }
    }

代码：一维

class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int row=triangle.size();
            int[] result=new int[row+1];
            for(int i=row-1;i>=0;i--)
            {
                for(int j=0;j<=i;j++)
                {
                    result[j]=Math.min(result[j],result[j+1])+triangle.get(i).get(j);
                }
            }
            return result[0];
        }
    }