当前位置: 首页 > 图灵资讯 > 技术篇> #yyds干货盘点# LeetCode程序员面试金典:三角形最小路径和

#yyds干货盘点# LeetCode程序员面试金典:三角形最小路径和

来源:图灵教育
时间:2023-06-04 09:22:09

题目:

给定三角形 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

代码实现:

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