LeetCode-120-三角形最小路径和
source link: https://segmentfault.com/a/1190000041001513
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode-120-三角形最小路径和
三角形最小路径和
解法一：动态规划题目描述：给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
使用一个数组记录到达每一层的结点的最小的路径和，然后动态规划的过程有以下依据：
- 每一层的第一个结点只能由上一层的第一个结点到达；
- 每一层的第 2 ~ size-1 个结点，可以由上一层相同位置或者上一个位置到达，取其中的较小值；
- 每一层的最后一个结点只能由上一层的最后一个节点到达。
最后，返回到达最后一层结点的最小路径和。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LeetCode_120 {
/**
* 动态规划
*
* @param triangle
* @return
*/
public static int minimumTotal(List<List<Integer>> triangle) {
// 记录到达每一层的每一个结点的路径和，初始化都是0
int[] result = new int[triangle.size()];
for (List<Integer> integers : triangle) {
// 记录到达当前层每一个结点的路径和，初始化都是0
int[] cur = new int[triangle.size()];
// 每一层的第一个结点只能由上一层的第一个结点到达
cur[0] = result[0] + integers.get(0);
int index;
for (index = 1; index < integers.size() - 1; index++) {
// 每一层的第 2 ~ size-1 个结点，可以有上一层相同位置或者上一个位置到达，取其中的较小值
cur[index] = integers.get(index) + Math.min(result[index - 1], result[index]);
}
if (index < integers.size()) {
// 每一层的最后一个结点只能由上一层的最后一个节点到达
cur[index] = integers.get(index) + result[index - 1];
}
result = cur;
}
// 最后，返回到达最后一层的最小的路径和的值
return Arrays.stream(result).min().getAsInt();
}
public static void main(String[] args) {
List<List<Integer>> triangle = new ArrayList<>();
List<Integer> one = new ArrayList<>();
one.add(2);
triangle.add(one);
List<Integer> two = new ArrayList<>();
two.add(3);
two.add(4);
triangle.add(two);
List<Integer> three = new ArrayList<>();
three.add(6);
three.add(5);
three.add(7);
triangle.add(three);
List<Integer> four = new ArrayList<>();
four.add(4);
four.add(1);
four.add(8);
four.add(3);
triangle.add(four);
System.out.println(minimumTotal(triangle));
}
}【每日寄语】 你就把现在的辛苦，看成一种投资，是对未来的投资，你以后才会有舒舒服服的自由。
Recommend
-
39
原题 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,...
-
10
对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。 格式 该...
-
5
LeetCode 第 209 号问题：长度最小的子数组-程序员小吴 当前位置：程序员小吴 > LeetCodeAnimation > LeetCode 第 209 号问题：长度最小的子数...
-
2
LeetCode-064-最小路径和发布于 11 月 3 日最小路径和题目描述：给定一个包含非负整数的 m x n 网格 grid ，请找...
-
9
第一题 打乱数组package main import "math/rand" //leetcode submit region begin(Prohibi...
-
4
阻力最小路径 事物演变的规律，本质还是要朝阻力最小的地方去，而不可能期望苦口婆心的劝说，让大家都能理性的选择符合自己长远利益的路径。 比如你不可能因为宣传吸烟有害健康，而期待别人戒烟; 不可能因为肥胖...
-
7
leetcode 76. 最小覆盖子串 发表于...
-
2
动态规划之最小路径和
-
4
二维数组的最小路径和问题 作者：Grey 原文地址: 博客园: 二...
-
3
#yyds干货盘点# 动态规划专题：矩阵的最小路径和 精选 原创 97的风 2022-10-25 11...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK