20天刷题计划-120. 三角形最小路径和

一、题目描述：

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 示例 2：

输入：triangle = [[-10]] 输出：-10  

提示：

1 <= triangle.length <= 200 triangle[0].length == 1 triangle[i].length == triangle[i - 1].length + 1 -104 <= triangle[i][j] <= 104  

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/tr…

二、思路分析：

题目中说的很清楚，每一步只能移动到下一行中相邻的结点上。 所以有如下几种情况，

• 情况一：在一行的最右边时，此时只有节点的正上方可以到达这个点，
  
• 情况二：在一行的最左边时，此时只有节点的左上方可以到达这个点
  
• 其他条件下，节点的正上方和左上方都可以到达这个点
  

具体过程：

初始化dp[i][j]为从开始到达位置 (i,j)的最小总和 第一层只有一个节点，没有其他选择，只能走这个节点，那么我们从我们从第二层开始，判断三种情况，然后遍历dp数组的最后一层，找到最小值，并返回

三、AC 代码：

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

四、总结：

掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐