120. 三角形最小路径和
https://leetcode.cn/problems/triangle/
难度中等1035
给定一个三角形 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 <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
进阶：
- 你可以只使用
O(n)的额外空间（n为三角形的总行数）来解决这个问题吗？
通过次数233,799提交次数340,920
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
//动态规划
//状态转移方程
int[][]arr = new int[triangle.size()][triangle.size()];
for(int i=0;i<triangle.size();i++)
{
for(int j=0;j<triangle.get(i).size();j++)
{
// System.out.println("i="+i+" j="+j+" "+triangle.get(i).get(j)+" "+triangle.get(i).size());
if(i==0 && j==0) arr[i][j] = triangle.get(i).get(j);
else if(j==0) arr[i][j] = arr[i][j]+arr[i-1][j]+triangle.get(i).get(j);
else if(j==triangle.get(i).size()-1) arr[i][j] =arr[i][j]+ arr[i-1][j-1]+triangle.get(i).get(j);
else arr[i][j] =arr[i][j]+Math.min(arr[i-1][j],arr[i-1][j-1])+triangle.get(i).get(j);
}
System.out.println();
}
for(int i=0;i<triangle.size();i++)
{
for(int j=0;j<triangle.size();j++)
{
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
int ans = arr[triangle.size()-1][0];
for(int j=0;j<triangle.size();j++)
{
if(ans>arr[triangle.size()-1][j])
{
ans= arr[triangle.size()-1][j];
}
}
return ans;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69093.html
