力扣120. 三角形最小路径和(Java 动态规划)

这篇具有很好参考价值的文章主要介绍了力扣120. 三角形最小路径和(Java 动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem: 120. 三角形最小路径和

题目描述

力扣120. 三角形最小路径和(Java 动态规划),力扣题目,leetcode,java,动态规划力扣120. 三角形最小路径和(Java 动态规划),力扣题目,leetcode,java,动态规划

思路

Problem:64. 最小路径和

本题目可以看作是在上述题目的基础上改编而来,具体的思路:

1.记录一个int类型的大小的 n 乘 n n乘n nn的数组(其中 n n n为数组triangle的行数)用于记录每一个当前阶段的最小路径和
2.大体上可以依据题意得出动态转移方程为dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);(其中i与j为遍历数组时的下标)即当前位置的最小路径和为其相邻左侧位置和左上方位置中的最小值加上数组triangle当前位置的值;
3.我们需要单独处理dp数组的第一列和dp
主对角线位置的值(由于dp可以看作为一个方阵,主对角线即为下标(i,i)位置的值)
:第一列依次向下累加;主对角线位置沿主对角线向下累加
3.我们仔细思考便可注意到,由于我们需要对主对角线的元素做一个单独的处理,而该处理会使得dp数组中最后一个位置不一定是最小路径和!!!(我们很容易想到,由于本题目是在求取三角形最小路径和因为我们在单独处理主对角线时不是由其相邻的正上方与正左侧共同得出所以在往下的动态转移过程中就不能确保当前位置就是当前整个决策阶段的最小值,但是我们可以得出对于整个阶段的最小值是存在于dp数组的最后一行的)所以我们求出dp数组中最后一行的最小值,即为给定三角形的最小路径和

解题方法

1.得出数组triangle的大小int n = triangle.size();;并定义int数组dp大小为 n 行 n 列 n行n列 nn
2.初始化dp数组第1行第1列位置(索引下标为(0,0))的值dp[0][0] = triangle.get(0).get(0);
3.从dp数组第二行开始执行动态转移方程,同时处理第一列和dp主对角线位置的值
4.求取dp数组最后一行的最小值并返回。

复杂度

时间复杂度:

O ( N × N ) O(N\times N) O(N×N)其中 N N N为数组triangle的大小

空间复杂度:

O ( N × N ) O(N\times N) O(N×N)文章来源地址https://www.toymoban.com/news/detail-813968.html

Code

class Solution {
    /**
     * The minimum path sum of triangles is obtained by dynamic programming
     * @param triangle Given martix
     * @return int
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        //Record the sum of the shortest paths
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            //Handle the Column 0
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
            //Dispose of (i, i)
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (dp[n - 1][i] < min) {
                min = dp[n - 1][i];
            }
        }
        return min;
    }
}

到了这里,关于力扣120. 三角形最小路径和(Java 动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【洛谷】数字三角形(动态规划)

    目录 边读边存 优化成一维数组——倒序没用了? 从上往下存,最大值存在最后一行,最后遍历最后一行得到最大值的写法  边读边存,可以有效降低时间复杂度 在上一篇文章(【洛谷】采药(01背包问题))将二维数组优化成一维数组的过程中,内层循环我们是采用倒序的方

    2024年02月16日
    浏览(39)
  • 动态规划入门(数字三角形模型)

    备战 2024年蓝桥杯算法学习 -- 每日一题 Python大学A组         试题一:摘花生         试题二:最低通行费用         试题三:方格取数         试题四:传纸条 【题目描述】         Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩

    2024年04月14日
    浏览(41)
  • 【题解 | 基础动态规划】:数字三角形

    链接: [USACO1.5] [IOI1994]数字三角形 Number Triangles 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中,从 7 → 3 → 8 → 7 → 5 7 to 3 to 8 to 7 to 5 7 →

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

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

    2024年02月11日
    浏览(62)
  • 数字三角形-蓝桥杯真题动态规划PYTHON解法

    目录 题目描述  解题思路 DP初始化 DP最终条件 DP初始条件 题目限制条件 总代码 首先映入我们眼帘的就是一个三角形,加求路径和最大,类似于找最短路径的题,很明显是一个二维数组的动态规划问题,对于动态规划问题我们只需要找好最终条件,初始条件(也就是特殊条件

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

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

    2024年04月14日
    浏览(57)
  • java打印各种三角形~(**版)

    文章目录 1、正等腰三角形 2、倒等腰三角形 3、菱形 4、左下直角三角形 5、右下直角三角形 6、左上直角三角形 7、右上直角三角形 8、数字版三角形  

    2024年02月07日
    浏览(47)
  • 数字三角形+包子凑数(蓝桥杯JAVA解法)

    题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。 输入描述 输入的第一行包含一个整数 N (1≤N≤

    2024年02月01日
    浏览(40)
  • Java用for循环打印三角形菱形

    目录   一、打印矩形  二、打印直角三角形 1.直角三角形  2.打印九九乘法表  三、打印等腰三角形  四、打印平行四边形  五、打印菱形  六、打印两个直角三角形 1.打印两个直角三角形  2.打印倒着的两个直角三角形 七、打印“蝴蝶”   一、打印矩形 运行结果:  二、

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

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

    2023年04月10日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包