面试算法100:三角形中最小路径之和

这篇具有很好参考价值的文章主要介绍了面试算法100:三角形中最小路径之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和的最小值为11,对应的路径经过的数字用阴影表示。
面试算法100:三角形中最小路径之和,算法,算法
说明:从三角形顶部到底部的路径数字之和的最小值为11,对应的路径经过的数字用阴影表示

分析

可以移动三角形每行的位置使它们左端对齐
面试算法100:三角形中最小路径之和,算法,算法
可以用f(i,j)表示从三角形的顶部出发到达行号和列号分别为i和j(i≥j)的位置时路径数字之和的最小值,同时用T[i][j]表示三角形行号和列号分别为i和j的数字。如果三角形中包含n行数字,那么f(n-1,j)的最小值就是整个问题的最优解。文章来源地址https://www.toymoban.com/news/detail-792485.html

public class Test {
    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(2);
        List<Integer> list2 = Arrays.asList(3, 4);
        List<Integer> list3 = Arrays.asList(6, 5, 7);
        List<Integer> list4 = Arrays.asList(4, 1, 8, 3);
        List<List<Integer>> triangle = Arrays.asList(list1, list2, list3, list4);
        int result = minimumTotal(triangle);
        System.out.println(result);

    }

    public static int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[][] dp = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle.get(i).get(j);
                if (i > 0 && j == 0) {// 最左边
                    dp[i][j] += dp[i - 1][j];
                }
                else if (i > 0 && i == j) {// 最右边
                    dp[i][j] += dp[i - 1][j - 1];
                }
                else if (i > 0) {
                    dp[i][j] += Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int num : dp[size - 1]) {// 答案在最底层,选出一个最小的
            min = Math.min(min, num);
        }
        return min;
    }
}

到了这里,关于面试算法100:三角形中最小路径之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 模型减面算法, 优化模型三角形

    sp4cerat/Fast-Quadric-Mesh-Simplification: Mesh triangle reduction using quadrics (github.com) https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification

    2023年04月24日
    浏览(31)
  • 「优选算法刷题」:有效三角形的个数

    给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 示例 1: 示例 2: 这道题,有一点挺新鲜的:构成三角形的三条边,仅需满足 2 条最短边之和大于等于第三条边即可。 以前的罗根,就总是傻傻地求 3 次😭 今天这道题,算是又打开了我新世

    2024年01月20日
    浏览(37)
  • 用动态规划算法编程实现数字三角形问题

    如下所示为一个数字三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 请编一个程序计算从顶至底的某一条路径,使该路径所经过的数字的总和最大。 思路:建立两个二位数组m(用来存储数字三角形),sum(用来存储数字三角形中每一个值得路径值);sum[i] [j]从最后一行开始存储; 如果当前

    2024年02月11日
    浏览(60)
  • 双指针算法实例5(有效三角形的个数)

    给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 示例 1: 示例 2: 提示: 1 = nums.length = 1000 0 = nums[i] = 1000 三角形构成条件:任意两边之和一定要大于第三边 其实在判断中,只需要判断 最小的两边和大于最长的一边 即可 假设 a=b=c 若要构成

    2024年02月11日
    浏览(40)
  • 【opencv】示例-minarea.cpp 如何寻找一组随机生成的点的最小外接矩形、三角形和圆...

    此段代码的主要功能是:利用OpenCV库生成随机点集,并计算并展示这些点的最小外包矩形、三角形和圆形。用户可以通过按键重新生成不同的随机点集,或者按ESC/Q退出程序。程序中利用了OpenCV的随机数生成函数、绘图函数以及几何形状的计算函数。

    2024年04月14日
    浏览(51)
  • 【算法专题突破】双指针 - 有效三角形的个数(5)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:611. 有效三角形的个数 - 力扣(Leetcode)  我们可以根据示例1来理解这一道题目, 他说数组里面的数可以组成三角形三条边的个数, 那我们先自己枚举一下所有情况看看:  【2, 2, 3】  【2, 2, 4】  【2,

    2024年02月10日
    浏览(44)
  • 贪心算法求数组中能组成三角形的最大周长

    题目:三角形的最大周长 给定由一些正数(代表长度)组成的数组arr,返回由其中三个长度组成的、面积不为零的三角形的最大周长。 如果不能形成任何面积不为零的三角形,返回`0。 分析: 对数组排序,再从大到小选择三个数, 再判断是否能构成三角形,可以直接返回三数之

    2024年02月12日
    浏览(46)
  • 使用Python实现高效数据下采样:详解最大三角形三桶(LTTB)算法

    引言 在我们接触大规模的数据集时,数据的数量往往会让人望而却步。数据分析、机器学习等领域的专业人员需要对这些数据进行处理,以便更好地理解数据,以及利用数据进行预测。然而,处理大规模数据的计算成本往往非常高,这时候,就需要引入下采样(Downsampling)的

    2024年02月14日
    浏览(38)
  • 【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字

       611. 有效三角形的个数 https://leetcode.cn/problems/valid-triangle-number/ 给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边    题

    2024年02月12日
    浏览(46)
  • 算法分析与设计-数字三角形问题(动态规划)(通俗易懂,附源码和图解,含时间复杂度分析)(c++)

    (一)题目 问题描述 给定一个由 n n n 行数字组成的数字三角形,如图所示。 试设计一个算法,计算从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 算法设计 对于给定的由 n n n 行数字组成的数字三角形,计算从该三角形的顶至底的路径经过的数字和的最大值

    2023年04月10日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包